Submission #42468

#	Time	Username	Problem	Language	Result	Execution time	Memory
42468		nonocut	Popeala (CEOI16_popeala)	C++14	100 / 100	372 ms	24656 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74