Submission #704819

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
704819	2023-03-03T04:28:56 Z	kelfert	Nafta (COI15_nafta)	C++17	Compilation error	0 ms	0 KB

nafta

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <random>
#include <chrono>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
typedef long long ll;

const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int N = 2010;

int cost[N][N], used[N][N], a[N][N], dp[N][N], cnt2[N];
 
void divide(int j, int l, int r, int ql, int qr) {
    if (l >= r) return;
    int m = (l + r) / 2;
    int opt;
    for (int i = ql; i < min(m, qr); i++) {
        if (dp[j][m] < dp[j - 1][i] + cost[i][m]) {
            dp[j][m] = dp[j - 1][i] + cost[i][m];
            opt = i;
        }
    }
    divide(j, l, m, ql, opt + 1);
    divide(j, m + 1, r, opt, qr);
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void dfs(int vx, int vy, int &sum, int &l, int &r) {
    used[vx][vy] = 1;
    sum += a[vx][vy];
    l = min(l, vy);
    r = max(r, vy);
    for (int k = 0; k < 4; k++) {
        int x = vx + dx[k], y = vy + dy[k];
        if (!used[x][y] && a[x][y] != -1) {
            dfs(x, y, sum, l, r);
        }
    }
} 

const int OPEN = 1;
const int CLOSE = -1;

struct Seg {
    int l, r, sum;
    Seg(int l, int r, int sum) : l(l), r(r), sum(sum) {}
    Seg() {}
};

struct Event {
    int x, id, tp, sum;
    Event(int x, int id, int tp, int sum) : x(x), id(id), tp(tp), sum(sum) {}
    Event() {}
};

bool comp(Event a, Event b) {
    return a.x < b.x;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            a[i][j] = -1;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < m; j++)
            if (s[j] != '.') a[i][j + 1] = (s[j] - '0');
    }
    vector<Seg> seg;
    vector<Event> events;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!used[i][j] && a[i][j] != -1) {
                int sum = 0, l = j, r = j;
                dfs(i, j, sum, l, r);
                seg.pb(Seg(l, r, sum));
                events.pb(Event(l, seg.size() - 1, OPEN, sum));
                events.pb(Event(r, seg.size() - 1, CLOSE, sum));
            }
        }
    }
    sort(all(events), comp);
    for (auto x : events) {
        if (x.tp == OPEN) cnt2[x.x] += x.sum;
    }
    int first = 0;
    for (int l = 0; l <= m; l++) {
        while (first < events.size() && events[first].x <= l) first++;
        int i = first, sum = 0;
        for (int r = l; r <= m; r++) {
            while (i < events.size() && events[i].x < r) {
                if (events[i].tp == OPEN) {
                    sum += events[i].sum;
                } else {
                    if (seg[events[i].id].l > l) sum -= events[i].sum;
                }
                i++;    
            }
            cost[l][r] = sum + cnt2[r];
            if (l == r) cost[l][r] = 0;
        }
    }
    for (int i = 0; i <= m; i++) 
        for (int j = 0; j <= m; j++) 
            dp[i][j] = -INF;
    dp[0][0] = 0;
    int ans = 0;
    for (int j = 1; j <= m; j++) {
        divide(j, 0, m + 1, 0, m + 1);
        ans = 0;
        for (int i = 1; i <= m; i++) ans = max(ans, dp[j][i]);
        cout << ans << "\n";
    }
    
    return 0;
}

Compilation message

In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
                 from /usr/include/c++/10/ext/atomicity.h:35,
                 from /usr/include/c++/10/bits/ios_base.h:39,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from nafta.cpp:6:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  121 | __gthrw(pthread_mutex_unlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  122 | __gthrw(pthread_mutex_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  123 | __gthrw(pthread_mutex_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  125 | __gthrw(pthread_cond_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  126 | __gthrw(pthread_cond_broadcast)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  127 | __gthrw(pthread_cond_signal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  128 | __gthrw(pthread_cond_wait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  129 | __gthrw(pthread_cond_timedwait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  130 | __gthrw(pthread_cond_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  132 | __gthrw(pthread_key_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  133 | __gthrw(pthread_key_delete)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  134 | __gthrw(pthread_mutexattr_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  135 | __gthrw(pthread_mutexattr_settype)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  136 | __gthrw(pthread_mutexattr_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
  237 | __gthrw2(__gthrw_(__pthread_key_create),
      |          ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
nafta.cpp: In function 'int main()':
nafta.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         while (first < events.size() && events[first].x <= l) first++;
      |                ~~~~~~^~~~~~~~~~~~~~~
nafta.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             while (i < events.size() && events[i].x < r) {
      |                    ~~^~~~~~~~~~~~~~~