Submission #260979

# Submission time Handle Problem Language Result Execution time Memory
260979 2020-08-11T09:01:43 Z Theo830 T-Covering (eJOI19_covering) C++17
0 / 100
28 ms 3832 KB
            #include <bits/stdc++.h>
            using namespace std;
            typedef long long ll;
            ll INF = 1e9+7;
            ll MOD = 998244353;
            typedef pair<ll,ll> ii;
            #define iii pair<ii,ll>
            #define f(i,a,b) for(long long i = a;i < b;i++)
            #define rf(i,a,b) for(long long i=a;i>=b;i--)
            #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
            #define w(t) while(t--)
            #define c(n); cin>>n;
            #define p(n) cout<<n;
            #define pl(n) cout<<n<<"\n";
            #define ps(n); cout<<n<<" ";
            #define F first
            #define S second
            #define pb(a) push_back(a)
            #define all(x) (x).begin(), (x).end()
            #define ull unsigned long long
            #define vll vector<ll>
            #define vii vector<ii>
            #define mkp make_pair
            #define ld long double
            #define arrin(a,n) f(i,0,n){cin>>a[i];}
            #define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
            #define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
            #define PI (2*acos(0))
            const long long N = 2e5+5;
            vll visit,dist,taken;
            vector<vll> adj;
            vector<vii> adj2;
            priority_queue<ii,vector<ii>, greater<ii> > pq;
            ll bit[N][2];
            ll siz;
            ll res = 0;
            ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
            ll gcd(ll a,ll b){return __gcd(a,b);}
            ll power(ll a,ll b){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
            ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
            void BITup(ll k, ll x,ll pos){while(k <= siz){bit[k][pos]^=x;k += k & -k;}}
            ll BITq(ll k,ll pos){ll s=0;while(k>=1){s^=bit[k][pos];k -= k &-k;}return s;}
            struct node{ll lazy=0,val=0;}seg[4000000];
            struct poll{ll x,y;};
            void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
            void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
            void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
            void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
            ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
            void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
            void filesin(void){freopen("a.txt","r",stdin);}
            void filesout(void){freopen("a.out","w",stdout);}
            int main(void){
                fastio;
                ll n,m;
                c(n);
                c(m);
                ll arr[n][m];
                f(i,0,n){
                    f(j,0,m){
                        c(arr[i][j]);
                    }
                }
                ll k;
                c(k);
                ll l[k],r[k];
                f(i,0,k){
                    c(l[i]);
                    c(r[i]);
                    if(l[i] == 0 || r[i] == 0){
                        pl("No");
                        return 0;
                    }
                    else if(l[i] == n-1 && r[i] == m-1){
                        pl("No");
                        return 0;
                    }
                }
                    ll ans = 0;
                    f(i,0,k){
                        ll x = l[i];
                        ll y = r[i];
                        ll res = arr[x][y];
                        ll sum = 0;
                        multiset<ll>s;
                        f(j,-1,2){
                            if(j != 0){
                                if(x+j >= 0 && x+j <= n-1){
                                    sum += arr[x+j][y];
                                    s.insert(arr[x+j][y]);
                                }
                                if(y+j >= 0 && y+j <= m-1){
                                    sum += arr[x][y+j];
                                    s.insert(arr[x][y+j]);
                                }
                            }
                        }
                        res += sum;
                      if(s.size() < 3){
                        cout<<"No";
                        return 0;
                      }
                        for(auto e:s){
                          if(s.size() == 4)
                            res -= e;
                            break;
                        }
                        ans += res;
                    }
                    pl(ans);
            }
            /*
            5 6
            7 3 8 1 0 9
            4 6 2 5 8 3
            1 9 7 3 9 5
            2 6 8 4 5 7
            3 8 2 7 3 6
            3
            1 1
            2 2
            3 4
            */

Compilation message

covering.cpp: In function 'int main()':
covering.cpp:104:27: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                           if(s.size() == 4)
                           ^~
covering.cpp:106:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                             break;
                             ^~~~~
covering.cpp: In function 'void filesin()':
covering.cpp:51:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             void filesin(void){freopen("a.txt","r",stdin);}
                                ~~~~~~~^~~~~~~~~~~~~~~~~~~
covering.cpp: In function 'void filesout()':
covering.cpp:52:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             void filesout(void){freopen("a.out","w",stdout);}
                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Incorrect 28 ms 3832 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -