oj.uz

답안 #127302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127302 2019-07-09T08:07:58 Z roseanne_pcy 조교 (CEOI16_popeala) C++14
17 / 100
 2000 ms 9036 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 maxn = 2e4+5;
const int maxt = 55;

ll pts[maxn];
int foo[maxt][maxn];

int n, t, s;

struct segtree
{
	ll st[4*maxn], lz[4*maxn];
	void push(int p, int L, int R)
	{
		if(!lz[p]) return;
		st[p] += lz[p];
		if(L != R)
		{
			lz[2*p] += lz[p];
			lz[2*p+1] += lz[p];
		}
		lz[p] = 0;
	}
	void update(int i, int j, int dx, int p = 1, int L = 0, int R = t)
	{
		push(p, L, R);
		if(i> R || j< L) return;
		if(i<= L && R<= j)
		{
			lz[p] += dx;
			push(p, L, R);
			return;
		}
		int M = (L+R)/2;
		update(i, j, dx, p<<1, L, M);
		update(i, j, dx, p<<1|1, M+1, R);
		st[p] = min(st[p<<1], st[p<<1|1]);
	}
	ll ask(int i, int j, int p = 1, int L = 0, int R = t)
	{
		if(i> R || j< L) return 1e9;
		push(p, L, R);
		if(i<= L && R<= j) return st[p];
		int M = (L+R)/2;
		ll x = ask(i, j, p<<1, L, M);
		ll y = ask(i, j, p<<1|1, M+1, R);
		return min(x, y);
	}
};

segtree ez[maxt];

ii rang[maxt];

ll dp[maxt][maxn];

int main()
{
	scanf("%d %d %d", &n, &t, &s);
	for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
	for(int i = 1; i<= n; i++)
	{
		char bar[maxn]; scanf("%s", bar+1);
		for(int j = 1; j<= t; j++) foo[i][j] = bar[j]-'0';
	}
	for(int i = 1; i<= n; i++) rang[i] = {-1, -1};
	ez[0].update(1, t, 1e9);
	for(int i = 1; i<= s; i++) ez[i].update(0, 0, 1e9);
	// printf("%lld\n", ez[1].ask(0, 0));
	for(int i = 1; i<= t; i++)
	{
		// printf("i = %d\n", i);
		for(int j = 1; j<= n; j++)
		{
			if(foo[j][i])
			{
				if(rang[j].X == -1)
				{
					rang[j] = {i, i};
				}
				else rang[j].Y = i;
				// printf("update [%d..%d] +%lld\n", rang[j].X-1, i-1, pts[i]);
				for(int k = 0; k<= s; k++) ez[k].update(rang[j].X-1, i-1, pts[i]);
			}
			else
			{
				if(rang[j].X == -1) continue;
				else
				{
					for(int k = rang[j].X; k<= rang[j].Y; k++)
					{
						// printf("[%d..%d] -%lld\n", rang[j].X-1, k-1, pts[k]);
						for(int k2 = 0; k2<= s; k2++) ez[k2].update(rang[j].X-1, k-1, -pts[k]);
					}
					rang[j] = {-1, -1};
				}				
			}
		}
		for(int rem = 1; rem<= s; rem++)
		{
			dp[rem][i] = ez[rem-1].ask(0, i-1);
			// printf("kuydp[%d][%d] = %lld\n", rem, i, dp[rem][i]);
			ez[rem].update(i, i, dp[rem][i]);
			// printf("k\n");
		}
	}
	for(int i = 1; i<= s; i++) printf("%lld\n", dp[i][t]);
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:68: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:69:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char bar[maxn]; scanf("%s", bar+1);
                   ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 2552 KB Output is correct
2 Correct 398 ms 2476 KB Output is correct
3 Correct 410 ms 2584 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 9036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 402 ms 2552 KB Output is correct
4 Correct 398 ms 2476 KB Output is correct
5 Correct 410 ms 2584 KB Output is correct
6 Execution timed out 2048 ms 9036 KB Time limit exceeded
7 Halted 0 ms 0 KB -