oj.uz

답안 #609580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609580 2022-07-27T17:34:33 Z UncoolAnon 조교 (CEOI16_popeala) C++14
0 / 100
 169 ms 2236 KB 
#include <bits/stdc++.h> 
#define int long long 
using namespace std; 
const int inf=3e9; 
 
signed main(){
	//freopen("in.txt","r",stdin); 
	int n,t,s; 
	cin>>n>>t>>s; 

	vector<vector<int>> dp(s+1,vector<int>(t+1,inf)); 
	vector<int> v(t); 
	for(int&x:v) cin>>x; 
	vector<int> prefix=v; 
	for(int i=1;i<t;i++) prefix[i]+=prefix[i-1]; 
	vector<vector<char>> a(n,vector<char>(t)); 
	for(int i=0;i<n;i++)
		for(int j=0;j<t;j++)
			cin>>a[i][j]; 
	vector<vector<int>> last(n,vector<int>(t,-1)); 
	for(int i=0;i<n;i++){
		for(int j=0;j<t;j++){
			if(a[i][j]=='0') last[i][j]=j;
			else if(j) last[i][j]=last[i][j-1]; 
		}
	}
	for(int i=0;i<t;i++){
		dp[1][i]=0; 
		int sum=0; 
		for(int contestant=0;contestant<n;contestant++)
			if(last[contestant][i]==-1) dp[1][i]+=prefix[i]; 

	}
	for(int subs=2;subs<=s;++subs){
		for(int testcase=0;testcase<t;testcase++){
			vector<int> pl; 
			for(int contestant=0;contestant<n;contestant++) pl.push_back(last[contestant][testcase]); 
			sort(pl.begin(),pl.end()); 
			int cnt=0; 
			for(int contestant=0;contestant<n;contestant++) cnt+=(a[contestant][testcase]=='1'); 
			if(testcase) dp[subs][testcase]=dp[subs-1][testcase-1]+v[testcase]*cnt; 
			for(int i=0;i<pl.size();i++){
				if(pl[i]==-1) continue; 
				if(pl[i]) dp[subs][testcase]=min(dp[subs][testcase],dp[subs-1][pl[i]-1]+(prefix[testcase]-prefix[pl[i]-1])*i);  
			}
		}
	}
	for(int i=1;i<=s;i++) cout<<dp[i][t-1]<<endl;
	return 0; 
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:29:7: warning: unused variable 'sum' [-Wunused-variable]
   29 |   int sum=0;
      |       ^~~
popeala.cpp:42:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i=0;i<pl.size();i++){
      |                ~^~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 169 ms 2236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -