kukudewen

kukudewen
22小时前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k)
{
f[0] = 0;
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ )
{
if (hh <= tt && q[hh] < i - k - 1) hh ++ ;
f[i] = f[q[hh]] + w[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

int res = INF;
for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]);

return res <= m;
}

int main()
{
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}

printf("%d\n", r);

return 0;
}


kukudewen
23小时前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 50010, INF = 1e9;

int n, m;
int w[N];
int f[N], q[N];

bool check(int k)
{
f[0] = 0;
int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ )
{
if (hh <= tt && q[hh] < i - k - 1) hh ++ ;
f[i] = f[q[hh]] + w[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

int res = INF;
for (int i = n - k; i <= n; i ++ ) res = min(res, f[i]);

return res <= m;
}

int main()
{
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}

printf("%d\n", r);

return 0;
}



kukudewen
23小时前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5+100;

int a[N];
LL s[N];
int q[N];
LL f[N];   //f[i] 表示在前i头牛中所有合法法案的最大效率值
int n,m;

LL g(int x){
return f[x-1] - s[x];
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;

for(int i = 1; i<=n; i++) {
cin>>a[i];
s[i] = s[i-1] + a[i];
}

int hh = 0, tt = 0;

for(int i = 1; i<=n; i++){
if(q[hh] < i-m) hh++;  //队头已经不在区间内
f[i] = max(f[i-1], g(q[hh])+ s[i]);
while(hh<=tt && g(q[tt]) <= g(i)) tt--;
q[++tt] = i;
}

cout<<f[n];

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, INF = 1e9;

int n, m, k;
int w[N][N];
int row_min[N][N], row_max[N][N];
int q[N];

void get_min(int a[], int b[], int tot)
{
int hh = 0, tt = -1;
for (int i = 1; i <= tot; i ++ )
{
if (hh <= tt && q[hh] <= i - k) hh ++ ;
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
b[i] = a[q[hh]];
}
}

void get_max(int a[], int b[], int tot)
{
int hh = 0, tt = -1;
for (int i = 1; i <= tot; i ++ )
{
if (hh <= tt && q[hh] <= i - k) hh ++ ;
while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
q[ ++ tt] = i;
b[i] = a[q[hh]];
}
}

int main()
{
scanf("%d%d%d", &n, &m, &k);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &w[i][j]);

for (int i = 1; i <= n; i ++ )
{
get_min(w[i], row_min[i], m);
get_max(w[i], row_max[i], m);
}

int res = INF;
int a[N], b[N], c[N];
for (int i = k; i <= m; i ++ )
{
for (int j = 1; j <= n; j ++ ) a[j] = row_min[j][i];
get_min(a, b, n);

for (int j = 1; j <= n; j ++ ) a[j] = row_max[j][i];
get_max(a, c, n);·

for (int j = k; j <= n; j ++ ) res = min(res, c[j] - b[j]);
}

printf("%d\n", res);

return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10, INF = 1e9;

int n, m;
int w[N], q[N];
int f[N];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

int hh = 0, tt = 0;
for (int i = 1; i <= n; i ++ )
{
if (q[hh] < i - m) hh ++ ;
f[i] = f[q[hh]] + w[i];
while (hh <= tt && f[q[tt]] >= f[i]) tt -- ;
q[ ++ tt] = i;
}

int res = INF;
for (int i = n - m + 1; i <= n; i ++ ) res = min(res, f[i]);

printf("%d\n", res);

return 0;
}



#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=300010;

int n,m;
int s[N],q[N];

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
s[i]+=s[i-1];
}

int res=-1e9;
int hh=0,tt=0;
for(int i=1;i<=n;i++)
{
if(q[hh]<i-m) hh++;
res=max(res,s[i]-s[q[hh]]);
while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
q[++tt]=i;
}
printf("%d\n",res);
return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
for (int i = 0; i < N; i ++ )
row[i] = col[i] = (1 << N) - 1;

for (int i = 0; i < 3; i ++ )
for (int j = 0; j < 3; j ++ )
cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
if (is_set) str[x * N + y] = '1' + t;
else str[x * N + y] = '.';

int v = 1 << t;
if (!is_set) v = -v;

row[x] -= v;
col[y] -= v;
cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
return x & -x;
}

int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
if (!cnt) return true;

int minv = 10;
int x, y;
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
if (str[i * N + j] == '.')
{
int state = get(i, j);
if (ones[state] < minv)
{
minv = ones[state];
x = i, y = j;
}
}

int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = map[lowbit(i)];
draw(x, y, t, true);
if (dfs(cnt - 1)) return true;
draw(x, y, t, false);
}

return false;
}

int main()
{
for (int i = 0; i < N; i ++ ) map[1 << i] = i;
for (int i = 0; i < 1 << N; i ++ )
for (int j = 0; j < N; j ++ )
ones[i] += i >> j & 1;

while (cin >> str, str[0] != 'e')
{
init();

int cnt = 0;
for (int i = 0, k = 0; i < N; i ++ )
for (int j = 0; j < N; j ++, k ++ )
if (str[k] != '.')
{
int t = str[k] - '1';
draw(i, j, t, true);
}
else cnt ++ ;

dfs(cnt);

puts(str);
}

return 0;
}



/*
0     1
2     3
4  5  6  7  8  9  10
11    12
13 14 15 16 17 18 19
20    21
22    23
*/

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 24;

int op[8][7] = {
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};

int oppsite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int q[N];
int path[100];

int f()
{
static int sum[4];
memset(sum, 0, sizeof sum);
for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;

int maxv = 0;
for (int i = 1; i <= 3; i ++ ) maxv = max(maxv, sum[i]);

return 8 - maxv;
}

void operate(int x)
{
int t = q[op[x][0]];
for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
q[op[x][6]] = t;
}

bool dfs(int depth, int max_depth, int last)
{
if (depth + f() > max_depth) return false;
if (f() == 0) return true;

for (int i = 0; i < 8; i ++ )
if (last != oppsite[i])
{
operate(i);
path[depth] = i;
if (dfs(depth + 1, max_depth, i)) return true;
operate(oppsite[i]);
}

return false;
}

int main()
{
while (cin >> q[0], q[0])
{
for (int i = 1; i < 24; i ++ ) cin >> q[i];

int depth = 0;
while (!dfs(0, depth, -1)) depth ++ ;

if (!depth) printf("No moves needed");
else
{
for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
}
printf("\n%d\n", q[6]);
}

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int q[N];
int w[5][N];

int f()
{
int cnt = 0;
for (int i = 0; i + 1 < n; i ++ )
if (q[i + 1] != q[i] + 1)
cnt ++ ;
return (cnt + 2) / 3;
}

bool dfs(int depth, int max_depth)
{
if (depth + f() > max_depth) return false;
if (!f()) return true;

for (int len = 1; len <= n; len ++ )
for (int l = 0; l + len - 1 < n; l ++ )
{
int r = l + len - 1;
for (int k = r + 1; k < n; k ++ )
{
memcpy(w[depth], q, sizeof q);
int x, y;
for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
if (dfs(depth + 1, max_depth)) return true;
memcpy(q, w[depth], sizeof q);
}
}

return false;
}

int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> q[i];

int depth = 0;
while (depth < 5 && !dfs(0, depth)) depth ++ ;
if (depth >= 5) puts("5 or more");
else cout << depth << endl;
}

return 0;
}



#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 46;

int n, m, k;
int w[N];
int weights[1 << 25], cnt = 1;
int ans;

void dfs1(int u, int s)
{
if (u == k)
{
weights[cnt ++ ] = s;
return;
}

dfs1(u + 1, s);
if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);
}

void dfs2(int u, int s)
{
if (u >= n)
{
int l = 0, r = cnt - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if ((LL)s + weights[mid] <= m) l = mid;
else r = mid - 1;
}
ans = max(ans, s + weights[l]);
return;
}

dfs2(u + 1, s);
if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);
}

int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> w[i];

sort(w, w + n);
reverse(w, w + n);

k = n / 2 + 2;
dfs1(0, 0);

sort(weights, weights + cnt);
cnt = unique(weights, weights + cnt) - weights;

dfs2(k, 0);

cout << ans << endl;

return 0;
}