Submission #1106248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106248		modwwe	여별 열쇠 (JOI15_keys)	C++17	100 / 100	3 ms	4644 KiB

keys

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(i) (1<<i)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
};
void phongbeo();
const int inf = 1e18;
const int mod2 = 1e9+7;
const int  mod1 = 998244353;
const int base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0) x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};

int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,limit,w,l,r,last,root,cost;
int kk,invf;
int el = 19;

main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        //fou(task);
    }
    //  NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
    // checktime
}
bool cmp(ib a,ib b)
{
    return a.a<b.a;
}
int dp[2][2001][2];
vector<int> v;
ib d[4001];
int dp3[2001];
int c[2001];
ib a[2001];
int dp2[2001][2001];
void phongbeo()
{
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        cin>>a[i].a>>a[i].b,
            v.pb(a[i].a),
            v.pb(a[i].b);
    sort(v.begin(),v.end());
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n; i++)
        a[i].a=lower_bound(v.begin(),v.end(),a[i].a)-v.begin()+1,
            a[i].b=lower_bound(v.begin(),v.end(),a[i].b)-v.begin()+1,
                d[a[i].a]= {i,1},
                           d[a[i].b]= {i,2};
    s4=0;
    for(int i=0; i<v.size()-1; i++)
        if(d[i+1].b==2&&d[i+2].b==1)
            s4+=v[i+1]-v[i];

    for(int i=1; i<=n; i++)
    {
        if(!c[i])
        {
            ++dem;
            l=i;
            dem2=0;
            for(int g=0; g<=1; g++)
                for(int j=0; j<=k; j++)
                    for(int f=0; f<2; f++)
                        dp[g ][j][f]=-inf;
            dp[0][0][0]=0;
            while(!c[l])
            {
                c[l]=1;
                dem2=1-dem2;
                dem3++;
                for(int j=0; j<=k; j++)
                    for(int f=0; f<2; f++)
                        dp[dem2][j][f]=-inf;
                for(int j=0; j<=k; j++)
                    dp[dem2][j][0]=max(dp[1-dem2][j][0],dp[1-dem2][j][1]);
                for(int j=1; j<=k; j++)
                    dp[dem2][j][1]=max(dp[1-dem2][j-1][1]+v[a[l].a]-v[a[l].a-1],dp[1-dem2][j-1][0]);
                if(i==l)
                {
                    for(int j=1; j<=k; j++)
                        dp[dem2][j][1]=max(dp[1-dem2][j-1][1]+v[a[l].a]-v[a[l].a-1],dp[1-dem2][j-1][0]+v[a[l].a]-v[a[l].a-1]);
                }
                s3=lower_bound(v.begin(),v.end(),v[a[l].b-1])-v.begin();
                if(d[s3].b==2)
                {

                    for(int j=1; j<=k; j++)
                        dp[dem2][j][1]+=v[s3]-v[s3-1];
                    break;
                }
                l=d[s3].a;
            }
            for(int j=0; j<=dem3; j++)
            {
                dp2[dem][j]=max(dp[dem2][j][0],dp[dem2][j][1]);
            }
            c[dem]=dem3;
            dem3=0;
        }
    }
    s3=0;
    for(int i=1; i<=dem; i++)
    {
        for(int j=s3; j>=0; j--)
            for(int z=0; z<=c[i], z+j<=k; z++)
                dp3[j+z]=max(dp3[j+z],dp3[j]+dp2[i][z]);
        s3+=c[i];
    }
    s5=0;
    for(int j=0; j<=k; j++)
        s5=max(s5,dp3[j]);
    cout<<s4+s5+m-v.back()+v[0];
}

Compilation message (stderr)

keys.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main()
      | ^~~~
keys.cpp: In function 'void phongbeo()':
keys.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=0; i<v.size()-1; i++)
      |                  ~^~~~~~~~~~~
keys.cpp:166:27: warning: left operand of comma operator has no effect [-Wunused-value]
  166 |             for(int z=0; z<=c[i], z+j<=k; z++)
      |                          ~^~~~~~
keys.cpp: In function 'int main()':
keys.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
keys.cpp:76:9: note: in expansion of macro 'fin'
   76 |         fin(task);
      |         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90