Submission #116658

#TimeUsernameProblemLanguageResultExecution timeMemory
116658JohnTitorPopeala (CEOI16_popeala)C++11
100 / 100
1652 ms14932 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Popeala" int n, t, h; ll s[20001]; ll x[20001]; string p[51]; int nf[20001][51]; ll nc[20001][51]; ll f[20001]; int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(t); read(h); FOR(i, 1, t) read(s[i]); FOR(i, 1, t) x[i]=x[i-1]+s[i]; FOR(i, 1, n){ cin>>p[i]; p[i]='0'+p[i]; nf[t][i]=t+1; DFOR(j, t-1, 0) if(p[i][j+1]=='0') nf[j][i]=j+1; else nf[j][i]=nf[j+1][i]; } FOR(i, 1, t) f[i]=1e18; FOR(used, 1, h){ FOR(j, 0, t) FOR(i, 0, n) nc[j][i]=1e18; FFOR(i, 0, t) if(f[i]<1e18){ int cnt=n; vector <int> dt; FOR(j, 1, n) dt.pb(nf[i][j]); sort(dt.begin(), dt.end()); reverse(dt.begin(), dt.end()); int now=i+1; while(!dt.empty()){ while((!dt.empty())&&(dt.back()==now)) dt.pop_back(); nc[now][dt.size()]=min(nc[now][dt.size()], (ll)(f[i]-x[i]*dt.size())); now=dt.back(); } } FOR(i, 0, t) f[i]=1e18; FOR(i, 1, t){ FOR(c, 0, n){ nc[i][c]=min(nc[i][c], nc[i-1][c]); f[i]=min(f[i], x[i]*c+nc[i][c]); } } writeln(f[t]); } }

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:48:17: warning: unused variable 'cnt' [-Wunused-variable]
             int cnt=n;
                 ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...