Submission #1117554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117554		codexistent	Domino (COCI15_domino)	C++14	30 / 160	707 ms	44300 KiB

domino

#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define fs first
#define sc second
 
ll r, s = 0, sfx[18];
short n, g[MAXN][MAXN], k;
int m;
set<pair<ll, pair<pair<short, short>, bool>>> sd;
vector<pair<ll, pair<pair<short, short>, bool>>> d;
vector<int> vct;
bool v[MAXN][MAXN];
 
void recurse(short itr = 0, short i = -1, ll sm = 0){
  	if(sm + (sfx[2 * (k - itr)]) < s - r){
      return;
    }
    if(itr == k){ 
        r = min(r, s - sm);
        return;
    }
 
    FOR(i2, i + 1, m - 1){
        if(v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] || v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc]){
            continue;
        }
        v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = true;
        v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = true;
 
        recurse(itr + 1, i2, sm + d[i2].fs);
 
        v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = false;
        v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = false;
    }
}
 
int main(){
    cin >> n >> k;
    FOR(i, 1, n) FOR(j, 1, n) {
        cin >> g[i][j];
        v[i][j] = false;
        s += g[i][j];
      	vct.push_back(g[i][j]);
    }
  	sort(begin(vct), end(vct));
    sfx[2*k + 1] = 0;
  	for(ll i = 2*k; i >= 1; i--) sfx[i] = sfx[i + 1] + vct[vct.size() - 1 - (2*k - i)];
  
    r = s;
 
    FOR(i, 1, n) FOR(j, 1, n) {
        if(i != n) {
            if(sd.size() < (k - 1) * 7 + 1){
                sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
            }else if(g[i][j] + g[i + 1][j] > (*sd.begin()).fs){
                sd.erase(*sd.begin());
                sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
            }
        }
        if(j != n) {
            if(sd.size() < (k - 1) * 7 + 1){
                sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
            }else if(g[i][j] + g[i][j + 1] > (*sd.begin()).fs){
                sd.erase(*sd.begin());
                sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
            }
        }
    }
    for(auto i : sd) {
        d.push_back(i);
    }
 
    m = sd.size();
    recurse();
 
    cout << r << endl;
}

Compilation message (stderr)

domino.cpp: In function 'int main()':
domino.cpp:56:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, std::pair<std::pair<short int, short int>, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |             if(sd.size() < (k - 1) * 7 + 1){
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~
domino.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, std::pair<std::pair<short int, short int>, bool> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |             if(sd.size() < (k - 1) * 7 + 1){
      |                ~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10