답안 #364473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364473 2021-02-09T09:48:54 Z Falseee Nafta (COI15_nafta) C++17
34 / 100
1000 ms 51508 KB
#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=2010;
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 res[2005];
int C[2005][2005];
int before_dp[2005];
int current_dp[2005];
bool valid(int i, int j){
    return i>=0 && j >= 0 && i < n && j < m;
}
// dp undirected graph.
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(){

    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);
            }
        }
    }
    // REP(i, n){
    //     REP(j, m){
    //         cout << ids[i][j]  << " ";
    //     }
    //     cout << endl;
    // }
    --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));
   
    for(int i = 0; i < m; ++i){
        int cur = 0;
        bool used[t_id];
        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 && !used[events[cur].id]){
                    res+=events[cur].val;
                }else if(!used[events[cur].id]) res-=events[cur].val;
                ++cur;
            }

            C[i][j]=res;
            // cout << C[i][j] << " ";

        }
        // cout << endl;
    }
    memset(current_dp, 0, sizeof(current_dp));
    memset(before_dp, 0, sizeof(before_dp));

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



}

Compilation message

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);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 41 ms 5404 KB Output is correct
8 Correct 27 ms 5096 KB Output is correct
9 Correct 16 ms 5996 KB Output is correct
10 Correct 32 ms 4456 KB Output is correct
11 Correct 16 ms 4204 KB Output is correct
12 Correct 12 ms 4076 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 41 ms 5404 KB Output is correct
8 Correct 27 ms 5096 KB Output is correct
9 Correct 16 ms 5996 KB Output is correct
10 Correct 32 ms 4456 KB Output is correct
11 Correct 16 ms 4204 KB Output is correct
12 Correct 12 ms 4076 KB Output is correct
13 Execution timed out 1095 ms 51508 KB Time limit exceeded
14 Halted 0 ms 0 KB -