Submission #494351

#	Time	Username	Problem	Language	Result	Execution time	Memory
494351		fcmalkcin	Popeala (CEOI16_popeala)	C++17	0 / 100	333 ms	64120 KiB

popeala

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

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

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


const ll maxn=2e4+5;
const ll mod=1e9+7   ;
const ll base=3e18;

/// you will be the best but now you just are trash
/// goal 1/7

ll dp[maxn][53];
char a[53][maxn];
ll pre[53];
ll n;
ll pre1[53][maxn];

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k > o.k; }
	// hien tai dang la tim max neu muon tim min thi doi dau cho nay va o cho isect cx doi dau 1 lan nua
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less< > > {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k)
        {
            x->p = x->m < y->m ? inf : -inf;
            // o cho nay nhe cai x-> m > y->m thanh x->m <y->m
        }
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll get(ll x) {
		if (empty()) return base;
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
} fwt[maxn][53];

void update(ll x,ll p,ll val,ll val1)
{
    for (int i=x;i<=n;i+= i&(-i))
    {
        fwt[i][p].add(val1,val);
    }
}
ll get(ll x,ll p,ll sl)
{
    ll ans=base;
    for (int i=x;i;i-= i&(-i))
    {
        ans=min(ans,fwt[i][p].get(sl));
    }
    return ans;
}
ll f[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("popeala.in", "r"))
    {
        freopen("popeala.in", "r", stdin);
        freopen("popeala.out", "w", stdout);
    }
    ll  m, s;
    cin>> m>> n>> s;
    for (int i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        f[i]=f[i-1]+x;
    }
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=s;j++)
        {
            dp[i][j]=base;
        }
    }
    for (int t=0;t<=s;t++)
    {
        pre1[t][0]=base;
    }
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=s;j++)
        {
            ll val=dp[i-1][j];
            pre1[j][i]=min(pre1[j][i-1],dp[i-1][j]);
            if (val==base) continue;
            ll pos=i;
            update(pos,j,val,-f[i-1]);
           /* if (i<=1&&j==0)
            {
                cout <<pos<<" "<<val<<" "<<-f[i-1]<<" nch"<<endl;
            }*/

        }
        vector<pll> vt;
        ll mx=0;
        for (int t=1;t<=m;t++)
        {
            if (a[t][i]=='1')
            {
                pre[t]++;
                vt.pb(make_pair(pre[t],t));
                mx=max(mx,pre[t]);
                //cout <<pre[t]<<" "<<t<<" "<<i<<" chk1"<<endl;
            }
            else
            {
                pre[t]=0;
            }
        }
        sort(vt.rbegin(),vt.rend());
        for (int j=1;j<=s;j++)
        {
            dp[i][j]=pre1[j-1][i-mx];
            /*if (i<=3)
            {
                cout <<dp[i][j]<<" "<<i<<" "<<j<<" chk"<<endl;
            }*/
            for (ll t=0;t<vt.size();t++)
            {
                ll k=t;
                while (k<vt.size()&&vt[k].ff==vt[t].ff) k++;
                k--;
                ll nxt=0;
                if (k+1<vt.size()) nxt=vt[k+1].ff;
                ll st=i-nxt;
                ll valpre=dp[i][j];
                dp[i][j]=min(dp[i][j],get(st,j-1,t+1)+(k+1)*f[i]);
                t=k;
            }

        }
    }
    for (int i=1;i<=s;i++)
    {
        //dp[n][i]=max(0ll,dp[n][i]);
        cout <<dp[n][i]<<endl;
    }
}
/*1
10 6
0 9 16
0 6 2
1 5 10 15
*/

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:160:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             for (ll t=0;t<vt.size();t++)
      |                         ~^~~~~~~~~~
popeala.cpp:163:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |                 while (k<vt.size()&&vt[k].ff==vt[t].ff) k++;
      |                        ~^~~~~~~~~~
popeala.cpp:166:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |                 if (k+1<vt.size()) nxt=vt[k+1].ff;
      |                     ~~~^~~~~~~~~~
popeala.cpp:168:20: warning: unused variable 'valpre' [-Wunused-variable]
  168 |                 ll valpre=dp[i][j];
      |                    ^~~~~~
popeala.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("popeala.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen("popeala.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74