oj.uz

Submission #117987

# Submission time Handle Problem Language Result Execution time Memory
117987 2019-06-17T15:41:44 Z JohnTitor Dango Maker (JOI18_dango_maker) C++11
13 / 100
 3 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Dango"
int n, m;
string s[3000];
int f[6000][3];
int dp(vector <int> &x){
    reverse(x.begin(), x.end());
//    bug(x.size());
//    for(auto a: x) cerr<<a<<' ';
//    cerr<<'\n';
    FFOR(i, 0, x.size()) FFOR(j, 0, 3) f[i][j]=0;
    int ans=0;
    FFOR(i, 0, x.size()){
        if(x[i]&2){
            f[i][2]=1;
            if(i>0) f[i][2]=max(f[i][2], max(max(f[i-1][0], f[i-1][1]), f[i-1][2])+1);
        }
        if(x[i]&1){
            f[i][1]=1;
            if(i>0) f[i][1]=max(f[i][1], max(f[i-1][0], f[i-1][1])+1);
//            if(i>1) f[i][1]=max(f[i][1], max(f[i-2][0], f[i-2][1])+1);
//            if(i>2) f[i][1]=max(f[i][1], max(max(f[i-3][0], f[i-3][1]), f[i-3][2])+1);
        }
        if(i>0) f[i][0]=max(f[i][0], f[i-1][0]);
        if(i>0) f[i][0]=max(f[i][0], f[i-1][1]);
        if(i>2) f[i][0]=max(f[i][0], max(f[i-2][1], f[i-2][2]));
        ans=max(ans, f[i][0]);
        ans=max(ans, f[i][1]);
        ans=max(ans, f[i][2]);
    }
//    bug(ans);
    return ans;
}
bool g0(int i, int j){
    if(j+2>=m) return 0;
    return s[i][j]=='R'&&s[i][j+1]=='G'&&s[i][j+2]=='W';
}
bool g1(int i, int j){
    if(i+2>=n) return 0;
    return s[i][j]=='R'&&s[i+1][j]=='G'&&s[i+2][j]=='W';
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    cin>>n>>m;
    FFOR(i, 0, n) cin>>s[i];
    int ans=0;
    for(int i=0, j=0; (i<n)&&(j<m); j+=(i+1)==n, i=min(n-1, i+1)){
        vector <int> all;
        FFOR(k, 0, n){
            if(i-k<0) break;
            if(j+k>=m) break;
            int d=0;
            if(g0(i-k, j+k)) d^=1;
            if(g1(i-k, j+k)) d^=2;
            all.pb(d);
        }
        ans+=dp(all);
    }
    writeln(ans);
}

Compilation message

dango_maker.cpp: In function 'int dp(std::vector<int>&)':
dango_maker.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
dango_maker.cpp:28:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, x.size()) FFOR(j, 0, 3) f[i][j]=0;
     ^~~~
dango_maker.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
dango_maker.cpp:30:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, x.size()){
     ^~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 2 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Incorrect 2 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -