oj.uz

Submission #127370

# Submission time Handle Problem Language Result Execution time Memory
127370 2019-07-09T09:27:28 Z roseanne_pcy Popeala (CEOI16_popeala) C++14
100 / 100
 367 ms 16652 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxt = 2e4+5;
const int maxn = 55;

ll pts[maxt];

char foo[maxn][maxt];

int n, t, s;

vector<int> lims[maxt];
ll mem[maxt];
ll dp[maxn][maxt];

void clear()
{
	for(int i = 0; i<= n; i++) mem[i] = 1e18+5;
}
int main()
{
	scanf("%d %d %d", &n, &t, &s);
	for(int i = 1; i<= t; i++)
	{
		scanf("%lld", &pts[i]);
		pts[i] += pts[i-1];
	}
	for(int i = 1; i<= n; i++)
	{
		scanf("%s", foo[i]+1);
	}
	for(int i = 1; i<= n; i++)
	{
		int last = 0;
		for(int j = 1; j<= t; j++)
		{
			if(foo[i][j] == '1')
			{
				lims[j].pb(last);
			}
			else
			{
				lims[j].pb(j);
				last = j; 
			}
		}
	}
	for(int i = 1; i<= t; i++)
	{
		lims[i].pb(i);
		sort(lims[i].begin(), lims[i].end());
	}
	for(int i = 0; i<= s; i++)
	{
		for(int j = 0; j<= t; j++)
		{
			dp[i][j] = 1e18;
		}
	}
	dp[0][0] = 0;
	for(int i = 1; i<= s; i++)
	{
		clear();
		for(int j = 1; j<= t; j++)
		{
			// printf("computing %d\n", j);
			for(int k = 0; k<= n; k++)
			{
				for(int run = j>1?lims[j-1][k]:0; run< lims[j][k]; run++)
				{
					mem[k] = min(mem[k], dp[i-1][run]-pts[run]*k);
					// if(k == 0) printf("cand2 %d-%d\n", dp[i-1][run], pts[run]*k);
				}
				// printf("[%d..%d), %d\n", j>1?lims[j-1][k]:0, lims[j][k], mem[k]);
				if(lims[j][k]> 0) dp[i][j] = min(dp[i][j], mem[k]+k*pts[j]);
				// printf("cand %d\n", mem[k]+k*pts[j]);
			}
			// printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
		}
		printf("%lld\n", dp[i][t]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:30: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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &pts[i]);
   ~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", foo[i]+1);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 932 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1656 KB Output is correct
2 Correct 12 ms 1656 KB Output is correct
3 Correct 12 ms 1688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2936 KB Output is correct
2 Correct 68 ms 3500 KB Output is correct
3 Correct 78 ms 4400 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 932 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct
3 Correct 13 ms 1656 KB Output is correct
4 Correct 12 ms 1656 KB Output is correct
5 Correct 12 ms 1688 KB Output is correct
6 Correct 50 ms 2936 KB Output is correct
7 Correct 68 ms 3500 KB Output is correct
8 Correct 78 ms 4400 KB Output is correct
9 Correct 103 ms 6364 KB Output is correct
10 Correct 164 ms 7936 KB Output is correct
11 Correct 288 ms 16440 KB Output is correct
12 Correct 299 ms 16632 KB Output is correct
13 Correct 366 ms 16632 KB Output is correct
14 Correct 367 ms 16524 KB Output is correct
15 Correct 366 ms 16652 KB Output is correct