oj.uz

Submission #127816

# Submission time Handle Problem Language Result Execution time Memory
127816 2019-07-10T06:43:57 Z sealnot123 Popeala (CEOI16_popeala) C++14
8 / 100
 11 ms 1784 KB 
#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 N = 20005, M = 52;
LL qs[N], MI[M][M], dp[N][M];
int P[M], PP[M], PPP[M], last[N][M];
char str[N];
int main(){
	int n, m, s;
	int i,j,k,l,a,b,c,d;
	scanf("%d%d%d",&m,&n,&s);
	for(i=1;i<=n;i++) dp[i][0] = 1e16;
	for(i=1;i<=s;i++) dp[0][i] = 1e16;
	for(i=1;i<=s;i++){
		for(j=0;j<=m;j++) MI[i][j] = 1e16;
	}
	for(i=1;i<=n;i++) scanf("%lld",&qs[i]), qs[i]+=qs[i-1];
	for(i=1;i<=m;i++){
		scanf(" %s",str+1);
		for(j=1;j<=n;j++){
			if(str[j] == '0') last[j][i] = j;
			else last[j][i] = last[j-1][i];
			/*printf("%d ",last[j][i]);*/
		}
		/*printf("\n");*/
		P[i] = 1;
	}
	for(i=0;i<=m;i++) PPP[i] = 1;
	for(i=1;i<=n;i++){
		PP[i] += m;
		for(j=1;j<=m;j++){
			while(P[j] <= last[i][j]) PP[P[j]++]--;
		}
		/*for(j=0;j<=n;j++) printf("%d ",PP[j]);
		printf("\n");*/
		for(j=0;j<=m;j++){
			while(PPP[j] <= i && PP[PPP[j]] <= j){
				a = PPP[j];
				for(k=1;k<=s;k++) MI[k][j] = min(MI[k][j], dp[a-1][k-1] - qs[a-1]*j);
				PPP[j]++;
			}
		}
		for(j=1;j<=s;j++){
			dp[i][j] = 1e16;
			for(k=0;k<=m;k++) dp[i][j] = min(dp[i][j], qs[i]*k + MI[j][k]);
		}
	}
	for(i=1;i<=s;i++) printf("%lld\n",dp[n][i]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:20:12: warning: unused variable 'l' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
            ^
popeala.cpp:20:16: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                ^
popeala.cpp:20:18: warning: unused variable 'c' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                  ^
popeala.cpp:20:20: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,l,a,b,c,d;
                    ^
popeala.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&m,&n,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:27:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=n;i++) scanf("%lld",&qs[i]), qs[i]+=qs[i-1];
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
popeala.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",str+1);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 5 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -