oj.uz

Submission #24826

# Submission time Handle Problem Language Result Execution time Memory
24826 2017-06-14T20:18:01 Z minimario Popeala (CEOI16_popeala) C++14
17 / 100
 139 ms 257356 KB 
#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 = 4005;
const int MAXN = 4005;

int pts[MAX], ptspref[MAX];
int correct[MAXN][MAX]; // [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[])
{
	/*
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	*/
	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]-1);
			trans[i].push_back(lastzero[j][i]);
			trans[i].push_back(lastzero[j][i]+1);

		}
		
		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

popeala.cpp: In function 'int main(int, const char**)':
popeala.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int sz=0; sz<trans[i].size(); sz++) {
                    ^
popeala.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k=0; k<trans[i].size(); k++) {
                   ^
popeala.cpp:34: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:37:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &pts[i]); 
                       ^
popeala.cpp:42: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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 252868 KB Output is correct
2 Correct 13 ms 252868 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 253924 KB Output is correct
2 Correct 49 ms 253924 KB Output is correct
3 Correct 56 ms 253924 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 257356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 252868 KB Output is correct
2 Correct 13 ms 252868 KB Output is correct
3 Correct 66 ms 253924 KB Output is correct
4 Correct 49 ms 253924 KB Output is correct
5 Correct 56 ms 253924 KB Output is correct
6 Incorrect 139 ms 257356 KB Output isn't correct
7 Halted 0 ms 0 KB -