oj.uz

Submission #962958

# Submission time Handle Problem Language Result Execution time Memory
962958 2024-04-14T10:13:23 Z MilosMilutinovic Popeala (CEOI16_popeala) C++14
100 / 100
 1532 ms 24408 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int inf=2e8;
int n,t,s,ntot;
int p[20005],nxt[55][20005],c[20005];
char r[55][20005];
ll dp[20005][55],pref[20005],mini[20005][55],cur[55];

int main(){
	n=readint(); t=readint(); s=readint();
	for(int i=1;i<=t;i++) p[i]=readint();
	for(int i=1;i<=n;i++) scanf("%s",r[i]+1);
	for(int i=1;i<=n;i++){
		int lst=t+1;
		for(int j=t;j>=1;j--){
			if(r[i][j]=='0') lst=j;
			nxt[i][j]=lst;
		}
	}
	for(int i=1;i<=t;i++) pref[i]=pref[i-1]+p[i];
	for(int i=0;i<=t;i++){
		for(int j=0;j<=s;j++){
			dp[i][j]=1e18;
		}
	}
	dp[0][0]=0;
	for(int j=1;j<=s;j++){
		for(int i=1;i<=t;i++){
			for(int k=0;k<=n;k++){
				mini[i][k]=(ll)1e18;
			}
		}
		for(int i=1;i<=t;i++){
			if(dp[i-1][j-1]==(ll)1e18) continue;
			vector<int> xs;
			xs.pb(i);
			xs.pb(t+1);
			for(int k=1;k<=n;k++){
				if(nxt[k][i]<=t) xs.pb(nxt[k][i]),c[nxt[k][i]]++;
			}
			sort(xs.begin(),xs.end());
			xs.erase(unique(xs.begin(),xs.end()),xs.end());
			int cnt=n;
			for(int p=0;p+1<(int)xs.size();p++){
				cnt-=c[xs[p]];
				chkmin(mini[xs[p]][cnt],dp[i-1][j-1]-pref[i-1]*1ll*cnt);
			}
			for(int p:xs) c[p]=0;
		}
		for(int i=0;i<=n;i++) cur[i]=(ll)1e18;
		for(int i=1;i<=t;i++){
			for(int k=0;k<=n;k++) chkmin(cur[k],mini[i][k]);
			for(int k=0;k<=n;k++) chkmin(dp[i][j],pref[i]*1ll*k+cur[k]);
		}
	}
	for(int i=1;i<=s;i++) printf("%lld\n",dp[t][i]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:35:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for(int i=1;i<=n;i++) scanf("%s",r[i]+1);
      |                        ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9052 KB Output is correct
2 Correct 34 ms 9052 KB Output is correct
3 Correct 35 ms 9048 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 9560 KB Output is correct
2 Correct 236 ms 10232 KB Output is correct
3 Correct 269 ms 12576 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 35 ms 9052 KB Output is correct
4 Correct 34 ms 9052 KB Output is correct
5 Correct 35 ms 9048 KB Output is correct
6 Correct 174 ms 9560 KB Output is correct
7 Correct 236 ms 10232 KB Output is correct
8 Correct 269 ms 12576 KB Output is correct
9 Correct 338 ms 14652 KB Output is correct
10 Correct 637 ms 14684 KB Output is correct
11 Correct 1161 ms 24276 KB Output is correct
12 Correct 1237 ms 24316 KB Output is correct
13 Correct 1416 ms 24312 KB Output is correct
14 Correct 1388 ms 24408 KB Output is correct
15 Correct 1532 ms 24312 KB Output is correct