oj.uz

Submission #49062

# Submission time Handle Problem Language Result Execution time Memory
49062 2018-05-21T14:56:51 Z Namnamseo Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 38428 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

char res[55][20010];
int T, N, S;

ll inf=(1ll<<60);
ll dp[55][20010];

int point[20010];
int pps[20010];

int sp[55];

struct TREE {
	static const int M = 32768;
	ll tree[M*2];
	
	void init(int I,int row){
		for(int i=0; i<=T; ++i){
			if(dp[I][i]==inf) tree[M+i]=inf;
			else tree[M+i]=dp[I][i]-row*pps[i];
		}
		for(int i=T+1; i<M; ++i) tree[M+i]=inf;
		for(int i=M-1; 1<=i; --i){
			tree[i]=min(tree[i*2], tree[i*2+1]);
		}
	}

	void init(){
		for(int i=0; i<2*M; ++i) tree[i]=inf;
	}

	TREE(){ init(); }

	void upd(int pos,ll val){
		pos += M;
		while(pos){
			tree[pos]=min(tree[pos], val);
			pos /= 2;
		}
	}

	ll range(int l,int r){
		ll ret=inf;
		l+=M; r+=M;
		while(l<=r){
			if(l%2==1) ret=min(ret, tree[l++]);
			if(r%2==0) ret=min(ret, tree[r--]);
			l/=2; r/=2;
		}
		return ret;
	}
} tr[52];

set<pp> tv;

int main(){
	
	//N=S=50; T=20000;
	read(N, T, S);
	for(int i=1; i<=T; ++i){
		scanf("%d", point+i);
		pps[i]=pps[i-1]+point[i];
	}

	for(int i=1; i<=N; ++i){
		scanf("%s",res[i]+1);
	}

	for(int i=1; i<=T; ++i) dp[0][i]=inf;
	for(int i=0; i<=N; ++i){
		tr[i].upd(0, 0);
	}

	for(int i=1; i<=S; ++i){
		for(int j=0; j<i; ++j) dp[i][j]=inf;
		for(int k=1; k<=N; ++k) sp[k]=0;
		tv.clear();
		for(int j=i; j<=T; ++j){
			for(int k=1; k<=N; ++k){
				if(res[k][j] == '0'){
					tv.erase({-sp[k], k});
					sp[k]=0;
				}
				else {
					if(sp[k]==0){
						sp[k]=j;
						tv.insert({-sp[k], k});
					}
				}
			}
			dp[i][j]=inf;
			int last=j;
			auto ai=tv.begin();

			int cnt=sz(tv);
			for(;ai!=tv.end();){
				auto bi=ai;
				int delta=0;
				for(; bi!=tv.end() &&
					ai->first == bi->first; ++bi) ++delta;

				int t=-ai->first-1;
				//printf("%d,%d / cnt %d t %d last %d\n", i,j,cnt,t,last);
				ll tmp = cnt*pps[j] + tr[cnt].range(t, last-1);
				//printf("tmp %d\n", tmp);

				dp[i][j] = min(dp[i][j], tmp);

				last=t;
				ai=bi;
				cnt -= delta;
			}

			if(0 <= last-1){
				//printf("zero %d\n", tr[0].range(0, last-1));
				dp[i][j] = min(dp[i][j], tr[0].range(0, last-1));
			}
			//fprintf(F, "%d ",dp[i][j]);
		}

		for(int k=0; k<=N; ++k){
			tr[k].init(i, k);
		}
		//fputc(10, F);
		printf("%lld\n", dp[i][T]);
	}
	/*fputs("hi", F);
	fclose(F);
	setbuf(stdout, 0);
	puts("NOW EASY");
	sysetm("./popeala_easy");
	sysetm("diff popeala_easy.out popeala.out");
	*/

	return 0;
}

Compilation message

popeala.cpp: In function 'void read(int&)':
popeala.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
popeala.cpp: In function 'void read(ll&)':
popeala.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~
popeala.cpp: In function 'int main()':
popeala.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", point+i);
   ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",res[i]+1);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27000 KB Output is correct
2 Correct 70 ms 27368 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 27864 KB Output is correct
2 Correct 559 ms 27980 KB Output is correct
3 Correct 315 ms 28180 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 28892 KB Output is correct
2 Correct 578 ms 29408 KB Output is correct
3 Correct 641 ms 30100 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27000 KB Output is correct
2 Correct 70 ms 27368 KB Output is correct
3 Correct 327 ms 27864 KB Output is correct
4 Correct 559 ms 27980 KB Output is correct
5 Correct 315 ms 28180 KB Output is correct
6 Correct 464 ms 28892 KB Output is correct
7 Correct 578 ms 29408 KB Output is correct
8 Correct 641 ms 30100 KB Output is correct
9 Correct 906 ms 31596 KB Output is correct
10 Correct 1080 ms 33044 KB Output is correct
11 Execution timed out 2089 ms 38428 KB Time limit exceeded
12 Halted 0 ms 0 KB -