oj.uz

Submission #582417

# Submission time Handle Problem Language Result Execution time Memory
582417 2022-06-23T17:58:22 Z TimDee Colouring a rectangle (eJOI19_colouring) C++14
30 / 100
 383 ms 102400 KB 
#include <bits/stdc++.h>
using namespace std;

#define paiu return
#define moment 0;
 
#define int long long
#define ll long long
 
#define forn(i,x) for (int i=0; i<x; i++)
 
#define vi(a,n) vector<int> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forn(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);

#define all(v) v.begin(),v.end()

#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
//const int maxn = 3e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

struct node {

    int sz=0,cost=0;
    vector<bitset<10>> a;

};

vector<node> v;
int n,m;

void bruteforce(vector<int>&a, vector<int>&b, node N, int i) {

    if (i==n+m-1) {
        v.pb(N);
        return;
    }

    bruteforce(a,b,N,i+1);
    if (i>=n+m-1) {
        //work with B
        N.cost+=b[i-n-m+1];
        if (i-n-m+1>=n) {
            //work with Bottom
            int y=i-n-m+1-n+1;
            int x=n-1;
            while (x>=0 && y<m) {
                N.sz+=1^N.a[x][y];
                N.a[x][y]=1;
                x--,y++;
            }
        } else {
            //work with Left
            int y=0;
            int x=i-n-m+1;
            while (x>=0 && y<m) {
                N.sz+=1^N.a[x][y];
                N.a[x][y]=1;
                x--,y++;
            }
        }
    } else {
        //work with A
        N.cost+=a[i];
        if (i<m) {
            //work with Top
            int y=m-1-i;
            int x=0;
            while (x<n && y<m) {
                N.sz+=1^N.a[x][y];
                N.a[x][y]=1;
                x++,y++;
            }
        } else {
            //work with Left
            int y=0;
            int x=i-m+1;
            while (x<n && y<m) {
                N.sz+=1^N.a[x][y];
                N.a[x][y]=1;
                x++,y++;
            }
        }
    }
    bruteforce(a,b,N,i+1);

}

void solve() {
    
    cin>>n>>m;

    //if (m==1) {
    //    //int ans=0;
    //    //vii(a,n);
    //    //vii(b,n);
    //    //forn(i,n) ans+=min(a[i],b[])
    //    //cout<<ans;
    //    //return;
    //    cout<<"ia liubliu apelsin\n";
    //    return;
    //}

    vii(md,m+n-1);
    vii(pd,m+n-1);

    if (n==1) {
        //exit(1);
        unsigned ll raspuns=0;
        reverse(all(pd));
        forn(I,n+m-1) {
            if (md[I] < pd[I]) raspuns+=md[I];
            else raspuns+=pd[I];
        }
        cout<<raspuns<<endl;
        return;
    }

    node zero;
    zero.a.resize(n);
    bruteforce(md,pd,zero,0);
    int ans=linf;

    forn(i,v.size()) {

        forn(j,n) {
            forn(k,m) {
                if (!v[i].a[j][k]) {
                    int I=j+k;

                    v[i].cost+=pd[I];
                    if (I>=n) {
                        //work with Bottom
                        int y=I-n+1;
                        int x=n-1;
                        while (x>=0 && y<m) {
                            v[i].a[x][y]=1;
                            x--,y++;
                        }
                    } else {
                        //work with Left
                        int y=0;
                        int x=I;
                        while (x>=0 && y<m) {
                            v[i].a[x][y]=1;
                            x--,y++;
                        }
                    }

                }
            }
        }
        ans=min(ans,v[i].cost);

    }
    cout<<ans;

}

int32_t main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //init_primes();
    
    int t=1;
    //cin>>t;
    
    while(t--) solve();
    
    paiu moment
}

Compilation message

colouring.cpp: In function 'void solve()':
colouring.cpp:10:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define forn(i,x) for (int i=0; i<x; i++)
......
  148 |     forn(i,v.size()) {
      |          ~~~~~~~~~~               
colouring.cpp:148:5: note: in expansion of macro 'forn'
  148 |     forn(i,v.size()) {
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 192 ms 70052 KB Output is correct
12 Correct 9 ms 2504 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 196 ms 70000 KB Output is correct
17 Correct 3 ms 1308 KB Output is correct
18 Correct 194 ms 70188 KB Output is correct
19 Correct 110 ms 31080 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 192 ms 70052 KB Output is correct
12 Correct 9 ms 2504 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 196 ms 70000 KB Output is correct
17 Correct 3 ms 1308 KB Output is correct
18 Correct 194 ms 70188 KB Output is correct
19 Correct 110 ms 31080 KB Output is correct
20 Runtime error 114 ms 102400 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 192 ms 70052 KB Output is correct
12 Correct 9 ms 2504 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 196 ms 70000 KB Output is correct
17 Correct 3 ms 1308 KB Output is correct
18 Correct 194 ms 70188 KB Output is correct
19 Correct 110 ms 31080 KB Output is correct
20 Runtime error 114 ms 102400 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4044 KB Output is correct
2 Correct 148 ms 7228 KB Output is correct
3 Correct 171 ms 7352 KB Output is correct
4 Correct 155 ms 7484 KB Output is correct
5 Correct 156 ms 7720 KB Output is correct
6 Correct 132 ms 6604 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 383 ms 102400 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 192 ms 70052 KB Output is correct
12 Correct 9 ms 2504 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 196 ms 70000 KB Output is correct
17 Correct 3 ms 1308 KB Output is correct
18 Correct 194 ms 70188 KB Output is correct
19 Correct 110 ms 31080 KB Output is correct
20 Runtime error 114 ms 102400 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -