Submission #364599

#	Time	Username	Problem	Language	Result	Execution time	Memory
364599		Falseee	Nafta (COI15_nafta)	C++17	34 / 100	1095 ms	47804 KiB

nafta

#include <bits/stdc++.h>
using namespace std;

//Optimizations
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//save time
#define endl '\n'
#define db(x) cerr << "> " << #x << ": " << x << endl
typedef long long ll;

//for sorting
#define all(a) a.begin(),a.end()

//Constants
#define PI   3.141592653593
#define MOD  1000000007LL
#define EPS  0.000000001
#define INF  0X3f3f3f3f

//loops
#define REP(i,n)      for(int i=0;i<(n);++i)
#define FOR(i,a,b)      for(int i=(a);i<(b);++i)
#define DFOR(i,a,b)     for(int i=(a);i>=(b);--i)

//vectors
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int,int>>
#define vlll vector<pair<ll,ll>>
#define pb  push_back
#define vb vector<bool>

//pairs
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define f first
#define s second

//fast I/O
#ifndef _WIN32
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define gc getchar
#define pc putchar

//If using cin and cout
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(NULL);cout.tie(NULL)

//queue
#define di deque<int>
#define dll deque<ll>
#define qi queue<int>
#define PQ priority_queue

//general
#define E empty()

const int MAXN=2001;
void usaco(string filename) {
    // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
	cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
	cin >> p.first;
	return cin >> p.second;
}
char g[MAXN][MAXN];
bool vis[MAXN][MAXN]= {false};
struct item{
    int l = INT_MAX;
    int r, value;
    item(){
        l = INT_MAX;
        r = INT_MIN;
        value = 0;
    }
    bool operator < (item & other){
        return l < other.l;
    }
};
struct event{
    bool start;
    int val, pos, id;
    bool operator < (event & other){
        return pos < other.pos;
    }
};


int ids[MAXN][MAXN];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cost[MAXN][MAXN];
int n, m;
int C[MAXN][MAXN];
int before_dp[MAXN];
int current_dp[MAXN];
bool valid(int i, int j){
    return i>=0 && j >= 0 && i < n && j < m;
}
void flood(int i, int j){
    vis[i][j]=1;
    REP(pos, 4){
        int ci = dx[pos]+i;
        int cj = dy[pos]+j;
        if(valid(ci, cj) && !vis[ci][cj] && g[ci][cj] != '.'){
            ids[ci][cj]=ids[i][j];
            flood(ci, cj);

        }

    }
}
int gres = 0;



void solve(int l, int r, int optl, int optr){

    if(l > r)
        return;
    int mid = (l+r) /2;
    pi best = {-1, -1};
    for(int k = optl ; k <= min(mid, optr); ++k){
        best = max(best, {before_dp[k]+C[k][mid], k});
    }
    current_dp[mid]=best.f;
    gres=max(gres, best.f);
    solve(l, mid-1, optl, best.s);
    solve(mid+1, r, best.s, optr);


}
int main(){
    IOS;
    TIE;
    cin >> n >> m;

    REP(i, n){
        REP(j, m){
            cin >> g[i][j];
        }
    }
    int t_id = 1;
    REP(i, n){
        REP(j, m){
            if(g[i][j]!= '.' && !vis[i][j]){
                ids[i][j] = t_id;
                vis[i][j]=1;
                ++t_id;
                flood(i,j);
            }
        }
    }

    --t_id;
    item ar[t_id];
    vector<event> events;
    REP(i, n){
        REP(j, m){
            if(ids[i][j])
            {
                ar[ids[i][j]-1].l = min(ar[ids[i][j]-1].l, j);
                ar[ids[i][j]-1].r = max(ar[ids[i][j]-1].r, j);
                ar[ids[i][j]-1].value+=g[i][j]-'0';
            }
        }
    }
    REP(i, t_id){
        events.pb({1, ar[i].value, ar[i].l, i});
        events.pb({0, ar[i].value, ar[i].r+1, i});
    }

    // sort(ar, ar+t_id);

    // cout << endl << endl;
    sort(all(events));

    bool used[t_id];
    for(int i = 0; i <= m; ++i){
        int cur = 0;
        memset(used, 0, sizeof(used));
        while(cur < (int)events.size() && events[cur].pos < i ){
            used[events[cur].id]=1;
            ++cur;
        }
        int res = 0;
        for(int j = 0; j <= m; ++j){
            while(cur < (int)events.size() && events[cur].pos < j){
                if(events[cur].start ){
                    res+=events[cur].val;
                }else if(!used[events[cur].id]) res-=events[cur].val;
                ++cur;
            }

            C[i][j]=res;
           

        }
    }
    memset(current_dp, 0, sizeof(current_dp));
    memset(before_dp, 0, sizeof(before_dp));

    for(int i = 0; i <m ; ++i){
        solve(i, m, i, m);
        swap(current_dp, before_dp);
        cout << gres << endl;
    }



}

Compilation message (stderr)

nafta.cpp: In function 'void usaco(std::string)':
nafta.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  freopen((filename + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:67:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  freopen((filename + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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