Submission #24823

#	Time	Username	Problem	Language	Result	Execution time	Memory
24823		minimario	Popeala (CEOI16_popeala)	C++14	17 / 100	66 ms	20988 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
  if ( !v.empty() ) {
    out << '[';
    std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "]";
  }
  return out;
}

const int INF = 2000000001;
const int MAX = 20005;
const int MAXN = 50;

int pts[MAX], ptspref[MAX];
int correct[MAX][MAXN]; // [1-t][1-n]
int prefcorrect[MAXN][MAX];

int dp[MAX][MAXN]; // [1-t][1-s]
int lastzero[MAXN][MAX];
vector<int> trans[MAX]; // transitions for each point
vector<int> points[MAX];

int main(int argc, char const *argv[])
{

	int n, t, s; scanf("%d %d %d", &n, &t, &s);
	for (int i = 1; i <= t; ++i)
	{
		scanf("%d", &pts[i]); 
		ptspref[i] = ptspref[i-1] + pts[i];
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<t; j++) {
			char c; scanf(" %c", &c);
			correct[i+1][j+1] = c - '0';
			prefcorrect[i+1][j+1] = prefcorrect[i+1][j] + correct[i+1][j+1];
		}
	}
	for (int i = 0; i < MAXN; ++i)
	{
		for (int j = 0; j < MAX; ++j)
		{
			lastzero[i][j] = 1; 
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=t; j++) {
			if (correct[i][j] == 0) { lastzero[i][j] = j; }
			else { lastzero[i][j] = lastzero[i][j-1]; }
	 	}
	}

	for (int i=1; i<=t; i++) {
		// from some x in trans[i] to i
		trans[i].push_back(i);
		for (int j=1; j<=s; j++) { 
			trans[i].push_back(j); 
		}
		
		for (int j=1; j<=n; j++) {
			trans[i].push_back(lastzero[j][i]);
		}
		
		sort(trans[i].begin(), trans[i].end());
		
		for (int sz=0; sz<trans[i].size(); sz++) {
			int j = trans[i][sz];
			int pts = 0;
			for (int k=1; k<=n; k++) {
				if (prefcorrect[k][i] - prefcorrect[k][j-1] == i-j+1) {
					pts += ptspref[i] - ptspref[j-1];
				}
			}
			points[i].push_back(pts);
		}
		//cout << trans[i] << endl;
		//cout << points[i] << endl;
		//cout << endl;
	}
	for (int i=0; i<MAX; i++) { 
		for (int j=0; j<MAXN; j++) {
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	for (int i=1; i<=t; i++) {
		for (int j=1; j<=s; j++) {
			for (int k=0; k<trans[i].size(); k++) {
				if (trans[i][k] > i || trans[i][k] <= 0) { continue; }
				dp[i][j] = min(dp[i][j], dp[trans[i][k]-1][j-1] + points[i][k]);
			}
			//cout << i << " " << j << " " << dp[i][j] << endl;
			if (i == t) { printf("%d\n", dp[i][j]); }
		}
	}	
	return 0;

}

Compilation message (stderr)

popeala.cpp: In function 'int main(int, const char**)':
popeala.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int sz=0; sz<trans[i].size(); sz++) {
                    ^
popeala.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k=0; k<trans[i].size(); k++) {
                   ^
popeala.cpp:31:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, t, s; scanf("%d %d %d", &n, &t, &s);
                                            ^
popeala.cpp:34:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &pts[i]); 
                       ^
popeala.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char c; scanf(" %c", &c);
                            ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74