Submission #1050186

#TimeUsernameProblemLanguageResultExecution timeMemory
1050186vjudge1Dango Maker (JOI18_dango_maker)C++17
13 / 100
61 ms142516 KiB
#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 (stderr)

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