oj.uz

Submission #417814

# Submission time Handle Problem Language Result Execution time Memory
417814 2021-06-04T10:50:30 Z AmineWeslati Dango Maker (JOI18_dango_maker) C++14
100 / 100
 847 ms 187052 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

const int MX=3010;
int N,M,g[MX][MX];

int memo[MX][MX][2][2];
int solve(int x, int y, int m, int m2){
	if(x<0 || y>=M) return 0;

	int &ind=memo[x][y][m][m2];
	if(ind!=-1) return ind; 

	int ans=solve(x-1,y+1,m2,0);
	//down
	if(x+2<N && g[x][y]==0 && g[x+1][y]==1 && g[x+2][y]==2){
		if(m+m2==0) ckmax(ans,solve(x-1,y+1,m2,0)+1);
	}

	//right
	if(y+2<M && g[x][y]==0 && g[x][y+1]==1 && g[x][y+2]==2){
		ckmax(ans,solve(x-1,y+1,m2,1)+1);
	}
	return ind=ans;
}

int main() {
    boost; IO();

    cin>>N>>M;
    FOR(i,0,N) FOR(j,0,M){
    	char c; cin>>c;
    	if(c=='R') g[i][j]=0;
    	else if(c=='G') g[i][j]=1;
    	else g[i][j]=2;
    }
    //FOR(i,0,N) FOR(j,0,M) cout << g[i][j] << " \n"[j==M-1];

    memset(memo,-1,sizeof(memo));
    int ans=0;
    FOR(i,0,N) ans+=solve(i,0,0,0);
    FOR(i,1,M) ans+=solve(N-1,i,0,0);
    cout << ans << endl;	
    

    return 0;
}
//Change your approach

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 142148 KB Output is correct
2 Correct 60 ms 142100 KB Output is correct
3 Correct 63 ms 142108 KB Output is correct
4 Correct 70 ms 142100 KB Output is correct
5 Correct 65 ms 142148 KB Output is correct
6 Correct 69 ms 142152 KB Output is correct
7 Correct 70 ms 142160 KB Output is correct
8 Correct 62 ms 142132 KB Output is correct
9 Correct 64 ms 142088 KB Output is correct
10 Correct 61 ms 142080 KB Output is correct
11 Correct 61 ms 142112 KB Output is correct
12 Correct 64 ms 142148 KB Output is correct
13 Correct 70 ms 142048 KB Output is correct
14 Correct 67 ms 142172 KB Output is correct
15 Correct 61 ms 142148 KB Output is correct
16 Correct 61 ms 142196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 142148 KB Output is correct
2 Correct 60 ms 142100 KB Output is correct
3 Correct 63 ms 142108 KB Output is correct
4 Correct 70 ms 142100 KB Output is correct
5 Correct 65 ms 142148 KB Output is correct
6 Correct 69 ms 142152 KB Output is correct
7 Correct 70 ms 142160 KB Output is correct
8 Correct 62 ms 142132 KB Output is correct
9 Correct 64 ms 142088 KB Output is correct
10 Correct 61 ms 142080 KB Output is correct
11 Correct 61 ms 142112 KB Output is correct
12 Correct 64 ms 142148 KB Output is correct
13 Correct 70 ms 142048 KB Output is correct
14 Correct 67 ms 142172 KB Output is correct
15 Correct 61 ms 142148 KB Output is correct
16 Correct 61 ms 142196 KB Output is correct
17 Correct 69 ms 142116 KB Output is correct
18 Correct 61 ms 142064 KB Output is correct
19 Correct 67 ms 142092 KB Output is correct
20 Correct 60 ms 142144 KB Output is correct
21 Correct 61 ms 142100 KB Output is correct
22 Correct 62 ms 142132 KB Output is correct
23 Correct 62 ms 142136 KB Output is correct
24 Correct 62 ms 142088 KB Output is correct
25 Correct 62 ms 142148 KB Output is correct
26 Correct 61 ms 142040 KB Output is correct
27 Correct 61 ms 142172 KB Output is correct
28 Correct 61 ms 142172 KB Output is correct
29 Correct 67 ms 142140 KB Output is correct
30 Correct 62 ms 142108 KB Output is correct
31 Correct 61 ms 142120 KB Output is correct
32 Correct 63 ms 142136 KB Output is correct
33 Correct 61 ms 142176 KB Output is correct
34 Correct 64 ms 142184 KB Output is correct
35 Correct 62 ms 142112 KB Output is correct
36 Correct 70 ms 142100 KB Output is correct
37 Correct 61 ms 142144 KB Output is correct
38 Correct 61 ms 142184 KB Output is correct
39 Correct 61 ms 142184 KB Output is correct
40 Correct 61 ms 142064 KB Output is correct
41 Correct 62 ms 142100 KB Output is correct
42 Correct 62 ms 142228 KB Output is correct
43 Correct 62 ms 142176 KB Output is correct
44 Correct 62 ms 142080 KB Output is correct
45 Correct 64 ms 142148 KB Output is correct
46 Correct 64 ms 142124 KB Output is correct
47 Correct 65 ms 142172 KB Output is correct
48 Correct 62 ms 142124 KB Output is correct
49 Correct 62 ms 142148 KB Output is correct
50 Correct 63 ms 142176 KB Output is correct
51 Correct 63 ms 142128 KB Output is correct
52 Correct 62 ms 142148 KB Output is correct
53 Correct 70 ms 142112 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 142148 KB Output is correct
2 Correct 60 ms 142100 KB Output is correct
3 Correct 63 ms 142108 KB Output is correct
4 Correct 70 ms 142100 KB Output is correct
5 Correct 65 ms 142148 KB Output is correct
6 Correct 69 ms 142152 KB Output is correct
7 Correct 70 ms 142160 KB Output is correct
8 Correct 62 ms 142132 KB Output is correct
9 Correct 64 ms 142088 KB Output is correct
10 Correct 61 ms 142080 KB Output is correct
11 Correct 61 ms 142112 KB Output is correct
12 Correct 64 ms 142148 KB Output is correct
13 Correct 70 ms 142048 KB Output is correct
14 Correct 67 ms 142172 KB Output is correct
15 Correct 61 ms 142148 KB Output is correct
16 Correct 61 ms 142196 KB Output is correct
17 Correct 69 ms 142116 KB Output is correct
18 Correct 61 ms 142064 KB Output is correct
19 Correct 67 ms 142092 KB Output is correct
20 Correct 60 ms 142144 KB Output is correct
21 Correct 61 ms 142100 KB Output is correct
22 Correct 62 ms 142132 KB Output is correct
23 Correct 62 ms 142136 KB Output is correct
24 Correct 62 ms 142088 KB Output is correct
25 Correct 62 ms 142148 KB Output is correct
26 Correct 61 ms 142040 KB Output is correct
27 Correct 61 ms 142172 KB Output is correct
28 Correct 61 ms 142172 KB Output is correct
29 Correct 67 ms 142140 KB Output is correct
30 Correct 62 ms 142108 KB Output is correct
31 Correct 61 ms 142120 KB Output is correct
32 Correct 63 ms 142136 KB Output is correct
33 Correct 61 ms 142176 KB Output is correct
34 Correct 64 ms 142184 KB Output is correct
35 Correct 62 ms 142112 KB Output is correct
36 Correct 70 ms 142100 KB Output is correct
37 Correct 61 ms 142144 KB Output is correct
38 Correct 61 ms 142184 KB Output is correct
39 Correct 61 ms 142184 KB Output is correct
40 Correct 61 ms 142064 KB Output is correct
41 Correct 62 ms 142100 KB Output is correct
42 Correct 62 ms 142228 KB Output is correct
43 Correct 62 ms 142176 KB Output is correct
44 Correct 62 ms 142080 KB Output is correct
45 Correct 64 ms 142148 KB Output is correct
46 Correct 64 ms 142124 KB Output is correct
47 Correct 65 ms 142172 KB Output is correct
48 Correct 62 ms 142124 KB Output is correct
49 Correct 62 ms 142148 KB Output is correct
50 Correct 63 ms 142176 KB Output is correct
51 Correct 63 ms 142128 KB Output is correct
52 Correct 62 ms 142148 KB Output is correct
53 Correct 70 ms 142112 KB Output is correct
54 Correct 62 ms 142060 KB Output is correct
55 Correct 71 ms 154136 KB Output is correct
56 Correct 63 ms 142132 KB Output is correct
57 Correct 65 ms 150140 KB Output is correct
58 Correct 138 ms 151072 KB Output is correct
59 Correct 777 ms 186696 KB Output is correct
60 Correct 788 ms 186564 KB Output is correct
61 Correct 792 ms 186648 KB Output is correct
62 Correct 72 ms 142092 KB Output is correct
63 Correct 778 ms 186424 KB Output is correct
64 Correct 812 ms 186700 KB Output is correct
65 Correct 806 ms 186576 KB Output is correct
66 Correct 847 ms 186692 KB Output is correct
67 Correct 648 ms 186604 KB Output is correct
68 Correct 647 ms 186584 KB Output is correct
69 Correct 649 ms 187052 KB Output is correct
70 Correct 138 ms 151144 KB Output is correct
71 Correct 139 ms 151264 KB Output is correct
72 Correct 135 ms 151112 KB Output is correct
73 Correct 133 ms 151124 KB Output is correct
74 Correct 134 ms 151084 KB Output is correct
75 Correct 142 ms 151108 KB Output is correct
76 Correct 134 ms 151208 KB Output is correct
77 Correct 135 ms 151080 KB Output is correct
78 Correct 135 ms 151028 KB Output is correct
79 Correct 134 ms 151104 KB Output is correct
80 Correct 144 ms 151324 KB Output is correct
81 Correct 133 ms 151032 KB Output is correct
82 Correct 134 ms 151148 KB Output is correct
83 Correct 138 ms 151072 KB Output is correct
84 Correct 138 ms 151284 KB Output is correct
85 Correct 133 ms 151072 KB Output is correct
86 Correct 133 ms 151040 KB Output is correct
87 Correct 133 ms 151056 KB Output is correct
88 Correct 133 ms 151032 KB Output is correct
89 Correct 135 ms 151032 KB Output is correct
90 Correct 134 ms 151200 KB Output is correct