oj.uz

Submission #1050186

# Submission time Handle Problem Language Result Execution time Memory
1050186 2024-08-09T07:54:10 Z vjudge1 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 61 ms 142516 KB 
#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
#define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 3010;
int n, m;
vector <vi> a(N, vi(N, 3));
vector <vi> b(N, vi(N, 3));

map<int, int> mp;


void solve() {
    cin>>n>>m;
    int k=1;
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=m; j++){
    		b[i][j]=k;
    		k++;
    		char c;
    		cin>>c;
    		if(c=='R'){
    			a[i][j]=0;
    		}
    		else if(c=='G'){
    			a[i][j]=1;
    		}
    		else{
    			a[i][j]=2;
    		}
    	}
    }
    
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=m-2; j++){
    		if(a[i][j]==0 and a[i][j+1]==1 and a[i][j+2]==2){
    			mp[b[i][j]]++;
    			mp[b[i][j+1]]++;
    			mp[b[i][j+2]]++;
    		}
    	}
    }
    for(int i=1; i<=n-2; i++){
    	for(int j=1; j<=m; j++){
    		if(a[i][j]==0 and a[i+1][j]==1 and a[i+2][j]==2){
    			mp[b[i][j]]++;
    			mp[b[i+1][j]]++;
    			mp[b[i+2][j]]++;
    		}
    	}
    }
    
    
    
    priority_queue <pair<int, tuple<int, int, int>>> q;
    
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=m; j++){
    		if(a[i][j]==0 and a[i][j+1]==1 and a[i][j+2]==2){
    			int temp = 1 + mp[b[i][j]]-1 + mp[b[i][j+1]]-1 + mp[b[i][j+2]]-1;
    			q.push({temp, make_tuple(b[i][j], b[i][j+1], b[i][j+2])});
    		}
    	}
    }
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=m; j++){
    		if(a[i][j]==0 and a[i+1][j]==1 and a[i+2][j]==2){
    			int temp = 1 + mp[b[i][j]]-1 + mp[b[i+1][j]]-1 + mp[b[i+2][j]]-1;
    			q.push({temp, make_tuple(b[i][j], b[i+1][j], b[i+2][j])});
    		}
    	}
    }
    
    
    int ans=0;
    while(!q.empty()){
    	pair<int, tuple<int, int, int>> top_element = q.top();
    	int mx = top_element.first;
        if(mx==1) break;
        q.pop();
        
        
		int second_tuple_first = get<0>(top_element.second);
        int second_tuple_second = get<1>(top_element.second);
        int second_tuple_third = get<2>(top_element.second);

		int temp = 1 + mp[second_tuple_first]-1 + mp[second_tuple_second]-1 + mp[second_tuple_third]-1;
		if(temp != mx){
			q.push({temp, top_element.second});
			continue;
		}
		
		mp[second_tuple_first]--;
		mp[second_tuple_second]--;
		mp[second_tuple_third]--;
		
		
    }
    
    cout<<q.size();
}

signed main() {
    fast_io;
    int tc = 1;
    // scanf("%d", &tc);
    while (tc--)
        solve();
}

Compilation message

dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:87:9: warning: unused variable 'ans' [-Wunused-variable]
   87 |     int ans=0;
      |         ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 142416 KB Output is correct
2 Correct 49 ms 142420 KB Output is correct
3 Correct 61 ms 142504 KB Output is correct
4 Correct 56 ms 142392 KB Output is correct
5 Correct 53 ms 142272 KB Output is correct
6 Correct 50 ms 142516 KB Output is correct
7 Correct 59 ms 142284 KB Output is correct
8 Correct 49 ms 142420 KB Output is correct
9 Correct 54 ms 142420 KB Output is correct
10 Correct 58 ms 142320 KB Output is correct
11 Correct 50 ms 142440 KB Output is correct
12 Correct 51 ms 142416 KB Output is correct
13 Correct 50 ms 142420 KB Output is correct
14 Correct 61 ms 142340 KB Output is correct
15 Correct 50 ms 142420 KB Output is correct
16 Correct 50 ms 142444 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 142416 KB Output is correct
2 Correct 49 ms 142420 KB Output is correct
3 Correct 61 ms 142504 KB Output is correct
4 Correct 56 ms 142392 KB Output is correct
5 Correct 53 ms 142272 KB Output is correct
6 Correct 50 ms 142516 KB Output is correct
7 Correct 59 ms 142284 KB Output is correct
8 Correct 49 ms 142420 KB Output is correct
9 Correct 54 ms 142420 KB Output is correct
10 Correct 58 ms 142320 KB Output is correct
11 Correct 50 ms 142440 KB Output is correct
12 Correct 51 ms 142416 KB Output is correct
13 Correct 50 ms 142420 KB Output is correct
14 Correct 61 ms 142340 KB Output is correct
15 Correct 50 ms 142420 KB Output is correct
16 Correct 50 ms 142444 KB Output is correct
17 Correct 50 ms 142428 KB Output is correct
18 Correct 54 ms 142368 KB Output is correct
19 Correct 51 ms 142416 KB Output is correct
20 Correct 50 ms 142420 KB Output is correct
21 Correct 50 ms 142516 KB Output is correct
22 Correct 52 ms 142420 KB Output is correct
23 Correct 50 ms 142424 KB Output is correct
24 Correct 56 ms 142404 KB Output is correct
25 Correct 50 ms 142344 KB Output is correct
26 Correct 55 ms 142416 KB Output is correct
27 Correct 50 ms 142348 KB Output is correct
28 Incorrect 50 ms 142500 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 142416 KB Output is correct
2 Correct 49 ms 142420 KB Output is correct
3 Correct 61 ms 142504 KB Output is correct
4 Correct 56 ms 142392 KB Output is correct
5 Correct 53 ms 142272 KB Output is correct
6 Correct 50 ms 142516 KB Output is correct
7 Correct 59 ms 142284 KB Output is correct
8 Correct 49 ms 142420 KB Output is correct
9 Correct 54 ms 142420 KB Output is correct
10 Correct 58 ms 142320 KB Output is correct
11 Correct 50 ms 142440 KB Output is correct
12 Correct 51 ms 142416 KB Output is correct
13 Correct 50 ms 142420 KB Output is correct
14 Correct 61 ms 142340 KB Output is correct
15 Correct 50 ms 142420 KB Output is correct
16 Correct 50 ms 142444 KB Output is correct
17 Correct 50 ms 142428 KB Output is correct
18 Correct 54 ms 142368 KB Output is correct
19 Correct 51 ms 142416 KB Output is correct
20 Correct 50 ms 142420 KB Output is correct
21 Correct 50 ms 142516 KB Output is correct
22 Correct 52 ms 142420 KB Output is correct
23 Correct 50 ms 142424 KB Output is correct
24 Correct 56 ms 142404 KB Output is correct
25 Correct 50 ms 142344 KB Output is correct
26 Correct 55 ms 142416 KB Output is correct
27 Correct 50 ms 142348 KB Output is correct
28 Incorrect 50 ms 142500 KB Output isn't correct
29 Halted 0 ms 0 KB -