提出 #72758126

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define rep(X,a,b) for(ll X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (ll)(a).size()
#define mem(a) memset(a,0,sizeof(a))
#define INF 9e18
#define EPS 1e-22
#define lc id<<1 
#define rc (id<<1)+1
#define ln seg[id].lnd
#define rn seg[id].rnd
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
typedef pair<long long,long long> pll;
typedef pair<pll,pll> pllll;
typedef pair<double,double> pdd;
typedef long long ll;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

pdd operator-(const pdd &a,const pdd &b){
    return mp(a.F-b.F,a.S-b.S);
}

double cross(const pdd &a,const pdd &b){
    return a.F*b.S-a.S*b.F;
}

struct maxFenwick {
    int n;
    vector<int> s;
    int lowbit(int x) { return x & -x; }
    maxFenwick(int _n) {
        n = _n + 1;
        s.clear(), s.resize(n, 0);
    }
    void update(int i, int v) {
        for (; i < n; i += lowbit(i))
            s[i] =max(s[i],v);
    }
    int query(int x) {
        int pre = -1;
        for (; x; x -= lowbit(x))
            pre=max(pre, s[x]);
        return pre;
    }
    maxFenwick(vector<int> a) {
        n = a.size();
        s.clear(), s.resize(n + 1, 0);
        for (int i = 1; i <= n; i++)
            update(i, a[i - 1]);
    }
};

typedef struct linkNode{
    int val;
    struct linkNode *back=nullptr,*next=nullptr;
}LinkNode;

typedef struct ball{
    ll size;
    struct ball *boss=nullptr;
}Ball;

Ball *find(Ball *_ball){
    if(_ball==nullptr)return nullptr;
    if(_ball->boss==_ball)return _ball;
    Ball *ret=find(_ball->boss);
    return ret;
}

void ballunion(Ball *u,Ball *v){
    Ball *ub=find(u),*vb=find(v);
    if(ub==vb)return;
    if(ub->size>vb->size)vb->boss=ub,ub->size+=vb->size;
    else ub->boss=vb,vb->size+=ub->size;
}

ll gcd(ll _a,ll _b){return _b?gcd(_b,_a%_b):_a;}

ll qpow(ll _x, ll _y,ll _P){
    ll _output=1;
    while(_y){
        if(_y&1)_output=(_output*_x)%_P;
        _x=(_x*_x)%_P;
        _y>>=1;
    }
    return _output;
}
    
ll v2(ll _x){
    return _x&-_x;
}

struct Node{
    ll info;
};

Node seg[800005];

void pull(ll id){seg[id].info=min(seg[lc].info,seg[rc].info);}

void modify(ll pos,ll v,ll L,ll R,ll id){
    if(pos==L&&R==pos){
        seg[id].info=v;
        return;
    }
    ll M=L+R>>1;
    if(pos<=M)modify(pos, v, L, M, lc);
    else modify(pos, v, M + 1, R, rc);
    pull(id);
}

ll query(ll l,ll r,ll L,ll R,ll id){
    if(l <= L && R <= r) return seg[id].info;
    int M=L+R>>1;
    if(r <= M) return query(l, r, L, M, lc);
    else if(l > M) return query(l, r, M + 1, R, rc);
    else return min(query(l, r, L, M, lc),query(l, r, M + 1, R, rc));
}

ll n,L,c[30005],a[30005][9],dp[30005],Max[30005],cnt,tmp[9],tmq[9];

void msort(ll l,ll r){
    if(r==l+1)return;
    ll m=l+r>>1;
    msort(l,m);
    msort(m,r);
    ll curi=l,curj=m,cur=l;
    while(curi<m&&curj<r){if(tmp[curi]<tmp[curj])tmq[cur++]=tmp[curi++],cnt+=r-curj;else tmq[cur++]=tmp[curj++];}
    while(curi<m)tmq[cur++]=tmp[curi++];while(curj<r)tmq[cur++]=tmp[curj++];
    rep(i,l,r)tmp[i]=tmq[i];
}

ll inrange(ll x,ll y){
    ll pos[10];
    rep(i,0,L){
        pos[a[x][i]]=i;
    }
    rep(i,0,L){
        tmp[i]=pos[a[y][i]];
    }
    /*printf("x:%lld y:%lld tmp:",x,y);
    rep(i,0,L){
        printf("%lld ",tmp[i]);
    }*/
    cnt=0;
    msort(0,L);
    //printf("cnt:%lld\n",cnt);
    return (L*(L-1)>>1)-cnt<=y-x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    scanf("%lld%lld",&n,&L);
    ++n;
    dp[0]=c[0]=0;
    rep(i,0,L){
        a[0][i]=i+1;
    }
    rep(i,1,n){
        scanf("%lld",&c[i]);
        dp[i]=c[i];
        rep(j,0,L){
            scanf("%lld",&a[i][j]);
        }
    }
    for(ll i=n-1;i>=0;--i){
        rep(j,i+1,min(n,i+40)){
            if(inrange(i,j))dp[i]=max(dp[i],c[i]+dp[j]);
        }
        if(i+40<n)dp[i]=max(dp[i],c[i]+Max[i+40]);
        Max[i]=max(Max[i+1],dp[i]);
    }
    printf("%lld\n",dp[0]);
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void err(std::istream_iterator<std::__cxx11::basic_string<char> >)':
./Main.cpp:26:35: warning: unused parameter 'it' [-Wunused-parameter]
   26 | void err(istream_iterator<string> it) {}
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~^~
./Main.cpp: In function 'void modify(ll, ll, ll, ll, ll)':
./Main.cpp:120:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |     ll M=L+R>>1;
      |          ~^~
./Main.cpp: In function 'll query(ll, ll, ll, ll, ll)':
./Main.cpp:128:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |     int M=L+R>>1;
      |           ~^~
./Main.cpp: In function 'void msort(ll, ll)':
./Main.cpp:138:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |     ll m=l+r>>1;
      |          ~^~
./Main.cpp:143:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  143 |     while(curi<m)tmq[cur++]=tmp[curi++];while(curj<r)tmq[cur++]=tmp[curj++];
      |     ^~~~~
./Main.cpp:143:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  143 |     while(curi<m)tmq[cur++]=tmp[curi++];while(curj<r)tmq[cur++]=tmp[curj++];
      |                                         ^~~~~

ジャッジ結果