제출 #1276421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276421		codefox	Nafta (COI15_nafta)	C++20	0 / 100	1 ms	332 KiB

nafta

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;
    
#define int long long
#define pii pair<int, int>

const int mod = 1e9+7;

void devide(int l, int r, int a, int b, vector<vector<int>> &cost, vector<vector<int>> &opt, vector<vector<int>> &dp, int k)
{
    int m = (l+r)/2;
    for (int j = a; j <= min(b, m); j++)
    {
        if (dp[k][j]+cost[m][j]>dp[k+1][m])
        {
            dp[k+1][m] = dp[k][j]+cost[m][j];
            opt[k+1][m] = j;
        }
    }
    if (l == r-1) return;
    devide(l, m, a, opt[k+1][m], cost, opt, dp, k);
    devide(m, r, opt[k+1][m], b, cost, opt, dp, k);
}

int32_t main()
{
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) cin >> grid[i];

    vector<vector<int>> vis(n, vector<int>(m, 0));
    vector<set<int>> groups(m);
    vector<int> gstart;
    vector<int> gsize;

    int k = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (vis[i][j] || grid[i][j]=='.') continue;
            gstart.push_back(1e9);
            gsize.push_back(0);
            queue<pii> q;
            q.push({i, j});
            while (q.size())
            {
                auto [a, b] = q.front();
                q.pop();
                if (a < 0 || a >= n) continue;
                if (b < 0 || b >= m) continue;
                if (vis[a][b] || grid[a][b]=='.') continue;
                vis[a][b] = 1;
                groups[b].insert(k);
                gsize[k]+=grid[a][b]-'0';
                gstart[k] = min(gstart[k], b);
                q.push({a-1, b});
                q.push({a+1, b});
                q.push({a, b-1});
                q.push({a, b+1});
            }
            k++;
        }
    }
    
    vector<vector<int>> cost(m, vector<int>(m, 0));
    vector<vector<int>> dp(m+1, vector<int>(m, 0));
    vector<vector<int>> opt(m+1, vector<int>(m, 0));

    for (int i = 0; i < m; i++)
    {
        priority_queue<pii, vector<pii>, less<pii>> pq;
        for (auto ele:groups[i]) pq.push({gstart[ele], gsize[ele]});
        int c = 0;
        for (int j = i-1; j >=0; j--)
        {
            while (pq.size() && pq.top().first>j)
            {
                c += pq.top().second;
                pq.pop();
            }   
            cost[i][j] = c;
        }
        while (pq.size())
        {
            c += pq.top().second;
            pq.pop();
        }   
        dp[1][i] = c;
    }

    for (int i = 1; i < m; i++)
    {
        devide(0, m, 0, m-1, cost, opt, dp, i);
        int mx = 0;
        for (int j = 0; j < m; j++) mx = max(mx, dp[i][j]);
        cout << mx << "\n";
    }
    int mx = 0;
    for (int j = 0; j < m; j++) mx = max(mx, dp[m][j]);
    cout << mx << "\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

nafta.cpp: In function 'int32_t main()':
nafta.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("../input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen("../output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66