oj.uz

Submission #42468

# Submission time Handle Problem Language Result Execution time Memory
42468 2018-02-27T13:11:58 Z nonocut Popeala (CEOI16_popeala) C++14
100 / 100
 372 ms 24656 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 2e9;
int n,m,s;
int a[55][20005];
int sum[20005];
int t[55];
vector<int> p[20005];
ll dp[20005], mn[55][60005];
int main() {
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++) {
        int val;
        scanf("%d",&val);
        sum[i] = sum[i-1] + val;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			char tc;
			scanf(" %c",&tc);
			a[i][j] = tc-'0';
		}
	}
	for(int x=1;x<=m;x++) {
		for(int i=1;i<=n;i++) {
			if(a[i][x]==0) t[i] = x;
			if(t[i]) p[x].push_back(t[i]);
		}
		p[x].push_back(0);
		sort(p[x].rbegin(),p[x].rend());
	}
	for(int x=1;x<=m;x++) dp[x] = inf;
	for(int k=1;k<=s;k++) {
        for(int x=0;x<=m;x++) dp[x] = inf;
		for(int x=1;x<=m;x++) {
			int val = n, last = x;
			for(auto y : p[x]) {
//                printf("\t%d * %d + %d [%d, %d]\n",val,sum[x],query(val,1,0,m,0,last-1),0,last-1);
				dp[x] = min(dp[x], (ll)val*sum[x] + mn[val][last-1]);
				val--; last = y;
			}
//            printf("dp %d = %d\n",x,dp[x]);
		}
		for(int val=0;val<=n;val++) {
            for(int x=0;x<=m;x++) {
                mn[val][x] = min((x ? mn[val][x-1] : inf), (ll)-val*sum[x] + dp[x]);
            }
		}
		printf("%d\n",dp[m]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:50:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("%d\n",dp[m]);
                      ^
popeala.cpp:12:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&s);
                          ^
popeala.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&val);
                         ^
popeala.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&tc);
                    ^

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1964 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 9 ms 1964 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3236 KB Output is correct
2 Correct 46 ms 4056 KB Output is correct
3 Correct 89 ms 4952 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 1248 KB Output is correct
3 Correct 14 ms 1964 KB Output is correct
4 Correct 8 ms 1964 KB Output is correct
5 Correct 9 ms 1964 KB Output is correct
6 Correct 34 ms 3236 KB Output is correct
7 Correct 46 ms 4056 KB Output is correct
8 Correct 89 ms 4952 KB Output is correct
9 Correct 108 ms 7272 KB Output is correct
10 Correct 124 ms 9432 KB Output is correct
11 Correct 372 ms 19792 KB Output is correct
12 Correct 359 ms 21252 KB Output is correct
13 Correct 297 ms 22628 KB Output is correct
14 Correct 342 ms 23588 KB Output is correct
15 Correct 294 ms 24656 KB Output is correct