| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26318 |
2017-06-29T07:25:32 Z |
서규호(#1103) |
Raspad (COI17_raspad) |
C++14 |
|
156 ms |
56496 KB |
#include <bits/stdc++.h>
#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define Inf 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus
using namespace std;
int N,M,nn; lld ans,sum;
int a[100002][52];
int where[100002][52];
int **when[100002];
char s[100];
int par[100];
int getpar(int x){
if(x == par[x]) return x;
return par[x] = getpar(par[x]);
}
void merge(int x,int y){
x = getpar(x); y = getpar(y);
par[x] = y;
}
void update(int node,int l,int r,lld s,lld e,lld value){
if(s > e) return;
sum += (e-s+1)*value;
}
int main(){
//freopen("input.txt","r",stdin);
scanf("%d %d",&N,&M);
for(nn=1; nn<N; nn*=2);
for(int i=1; i<=N; i++){
scanf("%s",s);
for(int j=1; j<=M; j++) a[i][j] = s[j-1]-'0';
}
for(int i=1; i<=N; i++){
vector<pp> tmp;
bool flag = false;
for(int j=1; j<=M+1; j++){
if(!flag && a[i][j] == 1){
flag = true;
tmp.pb({j,0});
}
if(flag && a[i][j] == 0){
flag = false;
tmp.back().second = j-1;
}
}
update(1,1,nn,i,i,tmp.size());
vector<pp> memo;
for(int j=0; j<tmp.size(); j++){
int s,e;
s = tmp[j].first; e = tmp[j].second;
vector<int> t;
for(int k=s; k<=e; k++){
where[i][k] = j;
if(a[i-1][k] == 1){
if(t.size() == 0) t.pb(where[i-1][k]);
else if(t.back() != where[i-1][k]) t.pb(where[i-1][k]);
}
}
if(t.size() == 0){
update(1,1,nn,1,i-1,1);
memo.pb({-1,-1});
}else{
memo.pb({t[0],t.back()});
}
vector<pair<int,pp>> calc;
for(int k=0; k<t.size(); k++) par[k] = k;
for(int k=0; k<(int)t.size()-1; k++){
for(int it=k+1; it<t.size(); it++){
calc.pb({when[i-1][t[k]][t[it]],{k,it}});
}
}
sort(calc.begin(),calc.end());
reverse(calc.begin(),calc.end());
for(auto &k : calc){
int x,y,z;
x = k.second.first; y = k.second.second;
z = k.first;
if(getpar(x) == getpar(y)) continue;
update(1,1,nn,z+1,i-1,-1);
merge(x,y);
}
}
when[i] = (int**)malloc(sizeof(int*)*tmp.size());
for(int j=0; j<(int)tmp.size()-1; j++){
when[i][j] = (int*)malloc(sizeof(int)*tmp.size());
int tt,it2;
tt = memo[j].second; it2 = j;
for(int it=j+1; it<tmp.size(); it++){
if(memo[j].first == -1 || memo[it].first == -1){
when[i][j][it] = 0;
}else{
if(tt >= memo[it].first){
when[i][j][it] = i-1;
tt = memo[it].second;
it2 = it;
}else{
when[i][j][it] = 0;
for(int itt=j; itt<=it2; itt++){
for(int k=memo[itt].first; k<=memo[itt].second; k++){
for(int t=memo[it].first; t<=memo[it].second; t++){
when[i][j][it] = max(when[i][j][it],when[i-1][k][t]);
}
}
}
}
}
}
}
ans += sum;
//printf("%lld\n",sum);
}
printf("%lld\n",ans);
return 0;
}
Compilation message
raspad.cpp: In function 'int main()':
raspad.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<tmp.size(); j++){
^
raspad.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<t.size(); k++) par[k] = k;
^
raspad.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int it=k+1; it<t.size(); it++){
^
raspad.cpp:99:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int it=j+1; it<tmp.size(); it++){
^
raspad.cpp:38:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&N,&M);
^
raspad.cpp:41:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",s);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
43432 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
43564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
43432 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
43564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45016 KB |
Output is correct |
| 2 |
Correct |
103 ms |
55312 KB |
Output is correct |
| 3 |
Incorrect |
156 ms |
56496 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
43432 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
43564 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
