#include <cstdio>
#include <iostream>
using namespace std;
int dp[51][20001];
long long ok[20010];
int val[20010],t,n;
pair <int,int> p[51][20010];
int aint[51][80001];
int logg[20010];
long long rmq[15][20010];
int last[20010];
int biti1 (long long x){
int sol = 0;
while (x){
sol = sol + (x&1);
x/=2;
}
return sol;
}
int query_rmq (int st,int dr){
int len = dr - st + 1;
if ((1<<logg[len]) == len)
return biti1(rmq[logg[len]][st]);
return biti1(rmq[logg[len]][st] & rmq[logg[len]][dr - (1<<logg[len])+1]);
}
void precalculare(){
int i,po,j,st,dr,mid;
for (i=1;i<=t;i++)
rmq[0][i] = ok[i];
for (po=1;po<=logg[t];po++){
for (i=1;i+(1<<po)-1<=t;i++)
rmq[po][i] = (rmq[po-1][i] & rmq[po-1][i+(1<<(po-1))]);
}
for (j=1;j<=t;j++){
p[n+1][j].first = j+1;
last[j] = n+1;
}
for (i=n;i>=0;i--){
for (j=t;j;j--){
if (query_rmq(p[last[j]][j].first-1 , j) == i){ /// exista un interval cu i biti
p[i][j].second = p[last[j]][j].first-1;
st = 1;
dr = p[i][j].second;
while (st<=dr){
mid = (st + dr)/2;
if (query_rmq(mid , j) != i)
st = mid + 1;
else dr = mid - 1;
}
p[i][j].first = st;
last[j] = i;
}
}
}
/// T log T + N * T * log T
}
void update (int b,int nod,int st,int dr,int poz,int x){
int mid = (st + dr)/2;
if (st == dr){
aint[b][nod] = x;
return;
}
if (poz<=mid)
update(b,2*nod,st,mid,poz,x);
else update (b,2*nod+1,mid+1,dr,poz,x);
aint[b][nod] = min(aint[b][2*nod] , aint[b][2*nod+1]);
}
int query (int b,int nod,int st,int dr,int x,int y){
int mid = (st + dr)/2;
int sol = 2000000000;
if (x<=st && dr<=y){
return aint[b][nod];
}
if (x<=mid)
sol = min(sol , query (b,2*nod,st,mid,x,y));
if (mid+1<=y)
sol = min(sol , query(b,2*nod+1,mid+1,dr,x,y));
return sol;
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int s,i,j,sk,b;
char x;
fscanf (fin,"%d%d%d",&n,&t,&s);
for (i=2;i<=20010;i++)
logg[i] = 1 + logg[i/2];
for (i=1;i<=t;i++){
fscanf (fin,"%d",&val[i]);
val[i]+=val[i-1];
}
long long p2 = 1;
for (i=1;i<=n;i++){
x = fgetc(fin);
for (j=1;j<=t;j++){
while (x != '0' && x != '1')
x= fgetc (fin);
ok[j]=p2 * (x-'0') + ok[j];
}
p2*=2;
}
int idk = ok[1];
for (i=1;i<=t;i++)
idk = (idk & ok[i]);
//printf ("%d ",idk);
precalculare();
for (sk=1;sk<=s;sk++){
for (i=1;i<=t;i++){
if (i<sk){
dp[sk][i] = 2000000000;
continue;
}
if (sk==1)
dp[sk][i] = (query_rmq(1,i) * val[i]);
else {
dp[sk][i] = 2000000000;
for (b=0;b<=n;b++){
if (p[b][i].first && p[b][i].second){
// if (p[b][i].first == 1 && p[b][i].first != p[b][i].second)
// p[b][i].first++;
dp[sk][i] = min(dp[sk][i],query (b,1,1,t,p[b][i].first,p[b][i].second) + b * val[i]);
}
}
}
}
dp[sk][0]=2000000000;
for (i=0;i<t;i++){
for (b=0;b<=n;b++){
if (dp[sk][i]!=2000000000)
update(b,1,1,t,i+1,dp[sk][i] - b * val[i]);
else update(b,1,1,t,i+1,dp[sk][i]);
}
}
}
for (j=1;j<=s;j++)
fprintf (fout,"%d\n",dp[j][t]);
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:93:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d",&n,&t,&s);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:97:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d",&val[i]);
~~~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:95:17: warning: iteration 20008 invokes undefined behavior [-Waggressive-loop-optimizations]
logg[i] = 1 + logg[i/2];
~~~~~~~~^~~~~~~~~~~~~~~
popeala.cpp:94:15: note: within this loop
for (i=2;i<=20010;i++)
~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
1272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
539 ms |
3320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
