Submission #127385

#	Time	Username	Problem	Language	Result	Execution time	Memory
127385		sealnot123	Popeala (CEOI16_popeala)	C++14	0 / 100	15 ms	2168 KiB

popeala

#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define push_back pb
#define emplace_back eb
using namespace std;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int T = 20007, N = 52;
LL dp[T][N], last[T][N], qs[T];
char str[T];
int n,t,s;
void play(int A, int l, int r, int ll, int rr){
	if(l>r) return ;
	int best;
	int m = (l+r)>>1;
	dp[m][A] = 1e16;
	int i,j,k;
	LL p = n;
	for(i = min(rr,m); i >= ll; i--){
		while(last[m][p] >= i) p--;
		if(dp[m][A] >= dp[i-1][A-1] + (qs[m]-qs[i-1])*p){
			dp[m][A] = dp[i-1][A-1] + (qs[m]-qs[i-1])*p;
			best = i;
		}
	}
	play(A, l, m-1, ll, best); play(A, m+1, r, best, rr);
}
int main(){
	int i,j,k,l,a,b,c,d;
	scanf("%d%d%d",&n,&t,&s);
	for(i=1;i<=t;i++) scanf("%lld",&qs[i]), qs[i]+=qs[i-1];
	for(i=1;i<=n;i++){
		scanf(" %s",str+1);
		for(j=1;j<=t;j++){
			if(str[j]=='1') last[j][i] = last[j-1][i];
			else last[j][i] = j;
			/*printf("%lld ",last[j][i]);*/
		}
		/*printf("\n");*/
	}
	for(i=1;i<=s;i++) dp[0][i] = 1e16;
	for(i=1;i<=t;i++){
		dp[i][0] = 1e16;
		sort(last[i]+1, last[i]+1+n);
	}
	for(i=1;i<=s;i++) play(i, 1, t, 1, t);
	for(i=1;i<=s;i++) printf("%lld\n",dp[t][i]);
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'void play(int, int, int, int, int)':
popeala.cpp:23:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k;
        ^
popeala.cpp:23:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
popeala.cpp: In function 'int main()':
popeala.cpp:35:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
          ^
popeala.cpp:35:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
popeala.cpp:35:14: warning: unused variable 'a' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
              ^
popeala.cpp:35:16: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                ^
popeala.cpp:35:18: warning: unused variable 'c' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                  ^
popeala.cpp:35:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
popeala.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&t,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:37:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=t;i++) scanf("%lld",&qs[i]), qs[i]+=qs[i-1];
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
popeala.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",str+1);
   ~~~~~^~~~~~~~~~~~~
popeala.cpp: In function 'void play(int, int, int, int, int)':
popeala.cpp:32:6: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  play(A, l, m-1, ll, best); play(A, m+1, r, best, rr);
  ~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74