# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
742379 | 2023-05-16T07:38:40 Z | jamielim | Gardening (RMI21_gardening) | C++14 | 199 ms | 18500 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; typedef vector<int> vi; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int t; ll n,m,k; typedef pair<ii,int> i3; map<i3,bool> memo; map<i3,int> jump; bool dp(int x,int y,int z){ if(z==0)return 1; if(x==1||y==1)return 0; // x=1 or y=1 but z>0 i3 p=mp(mp(x,y),z); if(memo.find(p)!=memo.end())return memo[p]; if(z>=x+y-2){ bool b=dp(x-1,y-1,z-(x+y-2)); if(b){ jump[p]=1; return memo[p]=1; } } if(dp(x,y-1,z)){ jump[p]=2; return memo[p]=1; }else if(dp(x-1,y,z)){ jump[p]=3; return memo[p]=1; } jump[p]=0; return memo[p]=0; } int main(){ scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&n,&m,&k); if(n%2==1||m%2==1||n*m<4*k||k<max(n,m)/2){ printf("NO\n"); continue; } int x=n/2,y=m/2,z=n*m/4-k; if(dp(x,y,z)){ printf("YES\n"); int arr[n][m]; memset(arr,-1,sizeof(arr)); int sx=0,ex=n-1,sy=0,ey=m-1; while(z!=0){ i3 p=mp(mp(x,y),z); if(jump[p]==1){ for(int i=sx;i<=ex;i++){ arr[i][sy]=k; arr[i][ey]=k; } for(int i=sy;i<=ey;i++){ arr[sx][i]=k; arr[ex][i]=k; } sx++;ex--;sy++;ey--; x--;y--;z-=(x+y); k--; }else if(jump[p]==2){ for(int i=0;i<x;i++){ arr[sx+2*i][ey-1]=k; arr[sx+2*i+1][ey-1]=k; arr[sx+2*i][ey]=k; arr[sx+2*i+1][ey]=k; k--; } ey-=2; y--; }else{ for(int i=0;i<y;i++){ arr[ex-1][sy+2*i]=k; arr[ex-1][sy+2*i+1]=k; arr[ex][sy+2*i]=k; arr[ex][sy+2*i+1]=k; k--; } ex-=2; x--; } } for(int i=0;i<(ex-sx+1)/2;i++){ for(int j=0;j<(ey-sy+1)/2;j++){ arr[sx+2*i][sy+2*j]=k; arr[sx+2*i][sy+2*j+1]=k; arr[sx+2*i+1][sy+2*j]=k; arr[sx+2*i+1][sy+2*j+1]=k; k--; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ printf("%d ",arr[i][j]); } printf("\n"); } }else printf("NO\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 612 KB | Correct! Azusa and Laika like the garden :) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 612 KB | Correct! Azusa and Laika like the garden :) |
2 | Correct | 11 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
3 | Correct | 12 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 612 KB | Correct! Azusa and Laika like the garden :) |
2 | Correct | 11 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
3 | Correct | 12 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
4 | Correct | 13 ms | 724 KB | Correct! Azusa and Laika like the garden :) |
5 | Correct | 13 ms | 616 KB | Correct! Azusa and Laika like the garden :) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 189 ms | 18268 KB | Correct! Azusa and Laika like the garden :) |
2 | Correct | 144 ms | 12856 KB | Correct! Azusa and Laika like the garden :) |
3 | Correct | 93 ms | 8924 KB | Correct! Azusa and Laika like the garden :) |
4 | Correct | 159 ms | 15452 KB | Correct! Azusa and Laika like the garden :) |
5 | Correct | 52 ms | 4852 KB | Correct! Azusa and Laika like the garden :) |
6 | Correct | 120 ms | 10880 KB | Correct! Azusa and Laika like the garden :) |
7 | Correct | 36 ms | 4052 KB | Correct! Azusa and Laika like the garden :) |
8 | Correct | 106 ms | 10720 KB | Correct! Azusa and Laika like the garden :) |
9 | Correct | 52 ms | 5960 KB | Correct! Azusa and Laika like the garden :) |
10 | Correct | 48 ms | 4880 KB | Correct! Azusa and Laika like the garden :) |
11 | Correct | 176 ms | 15620 KB | Correct! Azusa and Laika like the garden :) |
12 | Correct | 95 ms | 8828 KB | Correct! Azusa and Laika like the garden :) |
13 | Correct | 44 ms | 4792 KB | Correct! Azusa and Laika like the garden :) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
2 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
3 | Correct | 4 ms | 428 KB | Correct! Azusa and Laika like the garden :) |
4 | Correct | 6 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
5 | Correct | 6 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
6 | Correct | 4 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
7 | Correct | 4 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
8 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
9 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
10 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
11 | Correct | 3 ms | 340 KB | Correct! Azusa and Laika like the garden :) |
12 | Correct | 6 ms | 428 KB | Correct! Azusa and Laika like the garden :) |
13 | Correct | 8 ms | 1108 KB | Correct! Azusa and Laika like the garden :) |
14 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
15 | Correct | 4 ms | 500 KB | Correct! Azusa and Laika like the garden :) |
16 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
17 | Correct | 5 ms | 556 KB | Correct! Azusa and Laika like the garden :) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 612 KB | Correct! Azusa and Laika like the garden :) |
2 | Correct | 11 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
3 | Correct | 12 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
4 | Correct | 13 ms | 724 KB | Correct! Azusa and Laika like the garden :) |
5 | Correct | 13 ms | 616 KB | Correct! Azusa and Laika like the garden :) |
6 | Correct | 189 ms | 18268 KB | Correct! Azusa and Laika like the garden :) |
7 | Correct | 144 ms | 12856 KB | Correct! Azusa and Laika like the garden :) |
8 | Correct | 93 ms | 8924 KB | Correct! Azusa and Laika like the garden :) |
9 | Correct | 159 ms | 15452 KB | Correct! Azusa and Laika like the garden :) |
10 | Correct | 52 ms | 4852 KB | Correct! Azusa and Laika like the garden :) |
11 | Correct | 120 ms | 10880 KB | Correct! Azusa and Laika like the garden :) |
12 | Correct | 36 ms | 4052 KB | Correct! Azusa and Laika like the garden :) |
13 | Correct | 106 ms | 10720 KB | Correct! Azusa and Laika like the garden :) |
14 | Correct | 52 ms | 5960 KB | Correct! Azusa and Laika like the garden :) |
15 | Correct | 48 ms | 4880 KB | Correct! Azusa and Laika like the garden :) |
16 | Correct | 176 ms | 15620 KB | Correct! Azusa and Laika like the garden :) |
17 | Correct | 95 ms | 8828 KB | Correct! Azusa and Laika like the garden :) |
18 | Correct | 44 ms | 4792 KB | Correct! Azusa and Laika like the garden :) |
19 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
20 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
21 | Correct | 4 ms | 428 KB | Correct! Azusa and Laika like the garden :) |
22 | Correct | 6 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
23 | Correct | 6 ms | 596 KB | Correct! Azusa and Laika like the garden :) |
24 | Correct | 4 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
25 | Correct | 4 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
26 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
27 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
28 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
29 | Correct | 3 ms | 340 KB | Correct! Azusa and Laika like the garden :) |
30 | Correct | 6 ms | 428 KB | Correct! Azusa and Laika like the garden :) |
31 | Correct | 8 ms | 1108 KB | Correct! Azusa and Laika like the garden :) |
32 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
33 | Correct | 4 ms | 500 KB | Correct! Azusa and Laika like the garden :) |
34 | Correct | 5 ms | 468 KB | Correct! Azusa and Laika like the garden :) |
35 | Correct | 5 ms | 556 KB | Correct! Azusa and Laika like the garden :) |
36 | Correct | 29 ms | 2380 KB | Correct! Azusa and Laika like the garden :) |
37 | Correct | 37 ms | 3488 KB | Correct! Azusa and Laika like the garden :) |
38 | Correct | 57 ms | 6276 KB | Correct! Azusa and Laika like the garden :) |
39 | Correct | 75 ms | 7576 KB | Correct! Azusa and Laika like the garden :) |
40 | Correct | 19 ms | 1720 KB | Correct! Azusa and Laika like the garden :) |
41 | Correct | 47 ms | 5160 KB | Correct! Azusa and Laika like the garden :) |
42 | Correct | 138 ms | 13256 KB | Correct! Azusa and Laika like the garden :) |
43 | Correct | 117 ms | 11008 KB | Correct! Azusa and Laika like the garden :) |
44 | Correct | 41 ms | 4268 KB | Correct! Azusa and Laika like the garden :) |
45 | Correct | 199 ms | 18500 KB | Correct! Azusa and Laika like the garden :) |
46 | Correct | 27 ms | 2792 KB | Correct! Azusa and Laika like the garden :) |
47 | Correct | 25 ms | 2380 KB | Correct! Azusa and Laika like the garden :) |
48 | Correct | 57 ms | 6224 KB | Correct! Azusa and Laika like the garden :) |
49 | Correct | 62 ms | 5196 KB | Correct! Azusa and Laika like the garden :) |
50 | Correct | 129 ms | 11064 KB | Correct! Azusa and Laika like the garden :) |
51 | Correct | 109 ms | 10988 KB | Correct! Azusa and Laika like the garden :) |
52 | Correct | 71 ms | 7516 KB | Correct! Azusa and Laika like the garden :) |
53 | Correct | 22 ms | 2028 KB | Correct! Azusa and Laika like the garden :) |
54 | Correct | 60 ms | 6240 KB | Correct! Azusa and Laika like the garden :) |
55 | Correct | 52 ms | 5068 KB | Correct! Azusa and Laika like the garden :) |
56 | Correct | 74 ms | 7604 KB | Correct! Azusa and Laika like the garden :) |
57 | Correct | 35 ms | 2856 KB | Correct! Azusa and Laika like the garden :) |
58 | Correct | 21 ms | 1236 KB | Correct! Azusa and Laika like the garden :) |
59 | Correct | 27 ms | 1740 KB | Correct! Azusa and Laika like the garden :) |
60 | Correct | 79 ms | 7696 KB | Correct! Azusa and Laika like the garden :) |