Submission #118003

#	Time	Username	Problem	Language	Result	Execution time	Memory
118003		JohnTitor	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	732 ms	56152 KiB

dango_maker

#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());
//    for(int 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(f[i-1][0], 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>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>0) f[i][0]=max(f[i][0], f[i-1][2]);
        ans=max(ans, f[i][0]);
        ans=max(ans, f[i][1]);
        ans=max(ans, f[i][2]);
    }
    return ans;
}
bool good_right(int i, int j){
    if(i<0) return 0;
    if(j<0) return 0;
    if(j+2>=m) return 0;
    return (s[i][j]=='R')&&(s[i][j+1]=='G')&&(s[i][j+2]=='W');
}
bool good_down(int i, int j){
    if(i<0) return 0;
    if(j<0) return 0;
    if(i+2>=n) return 0;
    return (s[i][j]=='R')&&(s[i+1][j]=='G')&&(s[i+2][j]=='W');
}
int cnt[3000][3000];
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; (j<m); j+=((i+1)==n), i=min(n-1, i+1)){
        vector <int> all;
        FFOR(k, 0, 1e9){
            if(i-k<0) break;
            if(j+k>=m) break;
            cnt[i-k][j+k]++;
            int d=0;
            if(good_down(i-k-1, j+k)) d^=1;
            if(good_right(i-k, j+k-1)) d^=2;
//            if(d) assert(s[i][j]=='G');
            all.pb(d);
        }
        ans+=dp(all);
    }
//    FFOR(i, 0, n) FFOR(j, 0, m) cerr<<cnt[i][j]<<" \n"[j+1==m];
    writeln(ans);
}

Compilation message (stderr)

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:27: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:29:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, x.size()){
     ^~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67