akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <queue>

using namespace std;

#define N 3
#define N2 9

struct Puzzle {
  int f[N2];
  int space;
  string path;

  bool operator < (const Puzzle &p) const{
    for(int i = 0; i < N2; ++i){
      if(f[i] == p.f[i]) continue;
      return f[i] > p.f[i];
    }
    return false;
  }
};

static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'u', 'l', 'd', 'r'};

bool isTarget(Puzzle p){
  for(int i = 0; i < N2; i++)
    if(p.f[i] != (i + 1)) return false;
  return true;
}

string bfs(Puzzle s){
  queue<Puzzle> Q;
  map<Puzzle, bool> V;
  Puzzle u, v;
  s.path = "";
  Q.push(s);
  V[s] = true;

  while(!Q.empty()){
    u = Q.front(); Q.pop();
    if(isTarget(u)) return u.path;
    int sx = u.space / N;
    int sy = u.space % N;

    for(int r = 0; r < 4; ++r){
      int tx = sx + dx[r];
      int ty = sy + dy[r];
      if(tx < 0 || ty < 0 || tx >= N || ty >= N) continue;

      v = u;
      swap(v.f[u.space], v.f[tx * N + ty]);
      v.space = tx * N + ty;
      if(!V[v]){
        V[v] = true;
        v.path += dir[r];
        Q.push(v);

      }
    }
  }
  return "unsolvable";
}

int main() {
  Puzzle in;

  for(int i = 0; i < N2; ++i){
    cin >> in.f[i];
    if(in.f[i] == 0){
      in.f[i] = N2;
      in.space = i;
    }
  }
  string ans = bfs(in);
  cout << ans.size() << endl;

  return 0;
}



Measured memory_bytes: 30628
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

n = int(input())
dis = [-1] * n
info = [list(map(int, input().split())) for _ in range(n)]

stack = [[0, 0]]
ans = 0
while len(stack) > 0:
    num = stack.pop(0)
    if dis[num[0]] == -1:
        dis[num[0]] = num[1]
    for i in info[num[0]][2:]:
        if dis[i-1] == -1:
            stack.append([i - 1, num[1] + 1])
for i in range(n):
    print(str(i+1) + " " + str(dis[i]))



Measured memory_bytes: 13184
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long s = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 3 == 0 || i % 5 ==0) {
            continue;
        } else {
            s += i;
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
   int k,n;
   cin>>k>>n;
    bool arr[110]={false};
    for(int i=0;i<n;i++){
        int val;
        cin>>val;
        arr[val]=1;
    }
    int res=0,diff=INT_MAX;
    for(int i=0;i<110;i++){
        if(arr[i] == false){
            if(abs(k-i) < diff){
                res=i;
                diff=abs(k-i);
            }
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

ll maxi(ll a,ll b)
{
  if(a>b) return a;
  else return b;
}
ll mini(ll a,ll b)
{
  if(a>b) return b;
  else return a;
}

int main()
{
  ll H,W;
  cin>>H>>W;
  ll s1,s2,s3;
  ll smax=0,smin=1000000007,ans=1000000007;

  rep(h,H)
  {
    //縦割り
    s1=h*W;
    s2=(H-h)*(W/2);
    s3=H*W-s1-s2;
    smax=maxi(s1,maxi(s2,s3));
    smin=mini(s1,mini(s2,s3));
    ans=mini(ans,smax-smin);

    //横割り
    s1=h*W;
    s2=(H-h)/2*W;
    s3=H*W-s1-s2;
    smax=maxi(s1,maxi(s2,s3));
    smin=mini(s1,mini(s2,s3));
    ans=mini(ans,smax-smin);
  }
  swap(H,W);
  rep(h,H)
  {
    //縦割り
    s1=h*W;
    s2=(H-h)*(W/2);
    s3=H*W-s1-s2;
    smax=maxi(s1,maxi(s2,s3));
    smin=mini(s1,mini(s2,s3));
    ans=mini(ans,smax-smin);

    //横割り
    s1=h*W;
    s2=(H-h)/2*W;
    s3=H*W-s1-s2;
    smax=maxi(s1,maxi(s2,s3));
    smin=mini(s1,mini(s2,s3));
    ans=mini(ans,smax-smin);
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<queue>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> P;
typedef long long int ll;
typedef pair<ll,ll> LLP;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define INF 1000000000007
#define MOD 1000000007
#define ARRAY_MAX 3005


//重み付きUnion-Find
struct Potential_UnionFind{

    vector<int> par;
    vector<int> rank;
    vector<int> diff_weight;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        diff_weight.resize(n);
        REP(i,n){
            par[i] = i;
            rank[i] = 0;
            diff_weight[i] = 0;
        }
    }

    int root(int x) {//親を探す
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    int weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x,int y) {
        return root(x) == root(y);
    }

    void merge(int x, int y,int w) {

        int rx = root(x);
        int ry = root(y);
        
        if(rank[rx] < rank[ry]){
            diff_weight[rx] = -w - weight(x) + weight(y);
            par[rx] = ry;
        }else{
            diff_weight[ry] = w + weight(x) - weight(y);
            par[ry] = rx;
            if(rank[rx] == rank[ry]){
                rank[rx]++;
            }
        }
    }

    int diff(int x, int y) {
        return weight(y) - weight(x);
    }
};


int main(){

    Potential_UnionFind tree;
    int n,q;
    cin >> n >> q;
    tree.init(n);
    for(int i = 0;i < q;i++){

        int a,b,c,d;
        cin >> a;
        if(a == 0){
            cin >> b >> c >> d;
            tree.merge(b,c,d);
        }else{
            cin >> b >> c;
            if(tree.issame(b,c)){
                cout << tree.diff(b,c) << endl;
            }else{
                cout << "?" << endl;
            }
        }


    }


    return 0;
}


Measured memory_bytes: 3908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int64_t,int64_t> pll;
typedef vector<int64_t> vl;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
const long double PI = acos(-1);
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define ALL(a) begin(a),end(a)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

const int MAX=1010000;
ll fact[MAX],fact_inv[MAX];

ll power(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

void init(int n){
    fact[0]=1;
    for(int i=0;i<n;i++)fact[i+1]=fact[i]*(i+1)%mod;
    fact_inv[n]=power(fact[n],mod-2);
    for(int i=n-1;i>=0;i--)fact_inv[i]=fact_inv[i+1]*(i+1)%mod;
}

ll comb(ll n,ll r){
    return (fact[n]*fact_inv[r])%mod*fact_inv[n-r]%mod;
}

void solve() 
{   
    init(1010000);
    int x,y;cin>>x>>y;
    if((x+y)%3){cout<<0<<endl;return;}
    int m=(2*x-y)/3,n=(2*y-x)/3;
    if(n<0||m<0){cout<<0<<endl;return;}
    cout<<comb(n+m,n)<<endl;
}

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 16000
#include <stdio.h>

int main(void){
    int n;
    int nowX = 0,nowY = 0,count = 0;

    scanf("%d\n",&n);
    int time[n];
    int x[n];
    int y[n];
    for (int k = 0; k < n; ++k) {
        scanf("%d %d %d",&time[k],&x[k],&y[k]);
    }

    for (int i = 0; i < n; ++i) {
        count = 0;
        int timeCount;
        timeCount = time[i];
        if (i != 0){
            timeCount -= time[i - 1];
        }
        for (int j = 0; j < timeCount; ++j) {
            count++;
            if (x[i] > nowX){
                nowX += 1;
                continue;
            }
            else if(x[i] < nowX){
                nowX -= 1;
                continue;
            }
            else if(y[i] > nowY){
                nowY += 1;
                continue;
            }
            else if(y[i] <= nowY){
                nowY -= 1;
            }
        }
        if (nowX == x[i] && nowY == y[i])continue;

        printf("No");
        return 0;
    }
    printf("Yes");
    return 0;
}

Measured memory_bytes: 2848
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if(a > b) swap(a, b);
	if(b > c) swap(b, c);
	if(a == b && a == 5 && c == 7){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 128
// agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define mod 1000000007
#define endl '\n'
typedef long long int ll ;
using namespace std;

ll func(string s)
{
    ll ans=0;
    for(int i=0;i<s.size();i++){
        int j=i;
        ll cnt=0;
        while(s[i]==s[j]){
            cnt++;
            j++;
        }
        ans+=cnt/2;
        i=j-1;
    }
    return ans;
}
int main()
{
    string s;
    cin>>s;
    ll mo;
    cin>>mo;
    if(mo==1) {
        cout<<func(s); return 0; 
    }
    if(mo==2){
        s+=s;
        cout<<func(s); return 0; 
    }
    string str=s+s+s;
    int j=s.size()-1;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]==s[s.size()-1]) j=i;
        else break;
    }
    int k=s.size()-1;
    for(int i=s.size()-1;i<(2*s.size());i++)
    {
        if(str[i]==s[s.size()-1]) k=i;
        else break;
    }
    // cout<<j<<" "<<k<<endl;
    if(j==0 && k== (2*s.size())-1 ) {
        ll kjh= mo*s.size();
        kjh/=2;
        cout<<kjh<<endl;
        return 0;
        
    }
    ll mid=k-j+1;
    mid/=2;
    ll mada= mid*(mo-1);
    string temp;
    for(int i=0;i<j;i++){
        temp.push_back(s[i]);
    }
    ll left=func(temp);
    temp.clear();
    for(int i=k+1;i<(2*s.size());i++){
       temp.push_back(str[i]);
    }
    ll right=func(temp);
    ll val=s.size()+j;
    temp.clear();
    for(int i=k+1;i<val;i++) temp.push_back(str[i]);
    ll sx=   func(temp);
    sx=sx*(mo-2);
    // cout<<left<<" "<<right<<endl;
    ll ans= sx+left+right+mada;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 256
#include<stdio.h>
 
#define MAXLEN 20000
 
int garea,gareas[(MAXLEN/2)+1],gcnt,gend;
 
 
int getArea( char *inputs, int start, int end )
{
    int i;
    int ravine,water;
    
    gareas[gcnt]=ravine=water=0;
    for( i=start; i!=end; i++ ) {
        if( '\\'== *(inputs+i) ) {
           	water+=(ravine*2);
            ravine++;
            water++;
        } else if( 0 != ravine && '/' == *(inputs+i) ) {
        	ravine--;
        } else {
	     	water+=ravine;
        }       
    }
	gareas[gcnt]+=water;
    
    return gareas[gcnt];
}
  
int checkRavine( char *inputs, int start )
{
    int i;
    int ravine, minh, tmpi;
    
    ravine=0;
    tmpi=minh=MAXLEN;
    for( i=start; i<=gend && '\0'!=*(inputs+i); i++ ) {
        if( 0 <= ravine && '\\'== *(inputs+i) ) {
            ravine++;        
        } else if( 0 != ravine && '/' == *(inputs+i) ) {
            ravine--;
            if( ravine < minh ) {
        		minh=ravine;
        		tmpi=i;
            }
            if( 0 == ravine ) {
            	garea+=getArea( inputs, start, i+1 );
            	gcnt++;
			    gend=MAXLEN;           	
                return i-start;
            }
        }
    }
	gend=tmpi;
    if( MAXLEN==tmpi ) { gend=0; }
    return 0;
}
 
 
void getAreas( char *inputs )
{
    int i,next;
     
    next=0;
    for( i=0; i<=gend && '\0'!=inputs[i]; i++ ) {
    	if( '_' !=inputs[i] && '/' !=inputs[i] ) {
	        next=checkRavine( inputs, i );
	        i+=next;
        }
    }
 
    return;
}
 
int main( void ) 
{
    char inputs[MAXLEN+1];
    int i;
 
    scanf( "%s", inputs );
    garea=gcnt=0;
    gend=MAXLEN;
    getAreas( inputs );
     
    printf( "%d\n", garea );
    
    if( gcnt ) {
        printf( "%d ", gcnt );
        for( i=0; i<gcnt; i++ ) {
            printf( "%d", gareas[i] );
            if( i < gcnt-1 ) {
            	printf( " " );  
            }
        }
        printf( "\n" );
       
    } else {
        printf( "0\n" );
    }
     
    return 0;
}

Measured memory_bytes: 576
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int a, b, m;
    cin >> a >> b >> m;
    vector<int> A(a);
    vector<int> B(b);
    rep(i, a) cin >> A[i];
    rep(i, b) cin >> B[i];
    vector<int> x(m);
    vector<int> y(m);
    vector<int> c(m);
    rep(i, m) cin >> x[i] >> y[i] >> c[i];
    int ans =
        *min_element(A.begin(), A.end()) + *min_element(B.begin(), B.end());
    rep(i, m) chmin(ans, A[x[i] - 1] + B[y[i] - 1] - c[i]);
    cout << ans << endl;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,a,b;cin>>n>>a>>b;
  string win;
  if((b-a-1)%2==1) win="Alice"; else win="Borys";
  print(win);
  return 0;
}

Measured memory_bytes: 256
//BISMILLAHIR RAHMANIR RAHIM
//SOTO MEAW
//SOTO SONDESH
#include<bits/stdc++.h>

#define ls ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define __ <<" "<<
#define loop(m,n) for(m=0;m<n;m++)
#define case(z) "Case " << z++ << ": "
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define quit return 0

using namespace std;

void showmyDS(set<int> ds)
{
    set<int> ::iterator it;
    for (it=ds.begin();it!=ds.end();it++)
    {
        cout << *it << endl ;
    }
    cout << endl;
}
int main()
{
    ls
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //int t,l=1;cin>>t;while(t>0){
        ll int n;
        cin >> n ;
        ll int a[n],i,c=1,mn=INT_MAX;
        loop(i,n)
        {
            cin >> a[i];
            if(i==0)
                mn=a[i];
            else
            {
                if(a[i]<mn)
                {
                    c++;
                    mn=a[i];
                }
            }
        }
        cout<<c;
    //t--;}

    quit;
}


Measured memory_bytes: 5216
#include "iostream"
#include "cmath"
#include "iomanip"
using namespace std;

int main()
{
	double a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << fixed << setprecision(4) << sqrt((a - c)*(a - c) + (b - d)*(b - d)) << endl;
}


Measured memory_bytes: 3276
// N人目に注意!これだけ分けて考える。
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, x;
  cin >> N >> x;
  //ソートして小さい方から飴を与えていく
  vector<int> a(N);
  int ans = 0;
  for (int i = 0; i < N; i++) cin >> a.at(i);
  sort(a.begin(), a.end());
  for (int i = 0; i < N - 1; i++){
    if (a[i] <= x) {
      ++ans;
      x = x - a[i];
    }
  }
//答えが N になる場合というのは、x がちょうどぴったり a[i]の総和になっている場合のみにかぎられる。
  if (a[N-1] == x) ++ans;
  
    
   cout << ans << endl;
}
//追記:18行目でa[N]とa[N-1]を間違えた。頻発しているので添字が正しいかに気をつける
/* 後半の分岐は以下のように書くこともできる。
for (int i = 0; i < N; ++i) {
        if (x >= a[i]) ++res, x -= a[i];
        else break;
    }
    if (res == N && x) --res;
*/

Measured memory_bytes: 256
#include <bits/stdc++.h> 

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define int ll

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin>>N;
  vector<int>A(N+1),B(N);
  for(int i=0;i<N+1;i++)cin>>A[i];
  for(int i=0;i<N;i++)cin>>B[i];
  int c=0;
  for(int i=0;i<N;i++){
    c+=min(A[i],B[i]);
    c+=min(B[i]-min(A[i],B[i]),A[i+1]);
    A[i+1]=max(A[i+1]-(B[i]-min(A[i],B[i])),0ll);
  }
  cout<<c<<endl;
  return 0;
}


Measured memory_bytes: 1792
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int K,A,B;
  cin>>K>>A>>B;
  for(int i=A;i<=B;i++){
      if(i%K==0){
          cout<<"OK"<<endl;
          return 0;
      }

  }
  cout<<"NG"<<endl;
}

Measured memory_bytes: 3624
def gusuuhantei(i):
    count = 0
    num = i
    while True:
        if num % 2 ==0 and not num == 0:
            num = num / 2
            count += 1
        else:
            break
    return count
N = int(input())
li = [0]*(N+1)
for i in range(N+1):
    li[i] = gusuuhantei(i)
Maxcount = max(li)
index = li.index(Maxcount)
if N == 1:
    print(1)
else: 
    print(index)

Measured memory_bytes: 9288
from collections import deque


def main():
    n = int(input())
    a = [int(input()) for i in range(n)]

    a.sort()

    b = deque()
    for i in range(n//2):
        if i % 2:
            b.append(a[i])
            b.appendleft(a[n-i-1])
        else:
            b.append(a[n-i-1])
            b.appendleft(a[i])

    b_lst = list(b)
    ans = 0
    for i in range(n-2):
        ans += abs(b_lst[i+1]-b_lst[i])

    if n % 2:
        ans += max(abs(a[n//2]-b[0]), abs(a[n//2]-b[-1]))
    else:
        ans += abs(b[n-1]-b[n-2])

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9012
h,w=map(int,input().split())
ans=50000
for a,b in [(w,h),(h,w)]:
    for i in range(b):
        for c,d in [(a,b-i), (b-i,a)]:
            l=[i*a,c*(d//2),c*(d-d//2)]
            ans=min(ans,max(l)-min(l))
print(ans)

Measured memory_bytes: 3064
from bisect import bisect_left
from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]
G = deque([])
for i in range(N):
    a = A[i]
    ind = bisect_left(G,a)
    if ind==0:
        G.appendleft(a)
    else:
        G[ind-1] = a
print(len(G))

Measured memory_bytes: 8060
#include <bits/stdc++.h>
#define FASTIO
#define endl "\n" // Since endl forces a buffer flush which slows down large I/O operations.
#define ff first
#define ss second
#define pb push_back
#define input(c, n)             \
	for (int i = 0; i < (n); i++) \
		cin >> (c)[i];
#define exit_message(s) return 0 * printf(s)
#define show(c)           \
	for (auto i : (c))      \
		cout << i << " "; \
	cout << "\n";
#define display(c, n)           \
	for (int i = 0; i < (n); i++) \
		cout << (c)[i] << " ";    \
	cout << "\n";
#define forl(i, a, n) for (int (i) = (a); (i) < (n); (i)++)
#define dugbe(k) cout << "-\t> " << #k << " = " << k << "\n";

/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/

using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
typedef pair<ll, ll> prll;
typedef vector<int> vi;
typedef vector<ll> vill;
typedef vector<pr> vpr;
ifstream in("input.txt");
const ll mod = 1e9 + 7;

ll mod_pow(ll a, ll b)
{
	if (b == 0)
		return 1LL;

	ll res = mod_pow(a, b >> 1);
	res = (res * res) % mod;
	if (b & 1LL)
		res = (res * a) % mod;

	return res;
}

const int N = 1e5 + 5;

int n, m;
vi g[N];
int dp[N];

int longest_path(int s)
{
	if (dp[s] != -1)
		return dp[s];
	
	// cerr << "s : " << s << "\n";

	for (auto e: g[s])
	{
		dp[s] = max(dp[s], longest_path(e));
	}
	dp[s]++;
	return dp[s];
}

int32_t main()
{
#ifdef FASTIO
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#endif
	// freopen("in.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	memset(dp, -1, sizeof dp);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		ans = max(ans, longest_path(i));
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 7424
/*header*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define rep(i , x, p) for(int i = x;i <= p;++ i)
#define sep(i , x, p) for(int i = x;i >= p;-- i)
#define gc getchar()
#define pc putchar
#define int long long
#define mk make_pair
#define fi first
#define se second
using std::min;
using std::max;
using std::swap;
const int inf = 0x3f3f3f3f;

inline int gi() {
    int x = 0,f = 1;char c = gc;
    while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}return x * f;
}

void print(int x) {
    if(x < 0) pc('-') , x = -x;
    if(x >= 10) print(x / 10);
    pc(x % 10 + '0');
}

const int maxN = 200000 + 7;

const int inv2 = 500000004;
int f[4007][4007] , fac[maxN], a[maxN],b[maxN], inv[maxN];
const int mod = 1e9 + 7;

int Pow(int a,int b)
{
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1) ans=1ll*ans*a%mod;
    return ans;
}

void Pre() {
	fac[0] = 1;
	for(int i = 1;i <= 8000;++ i) 
    fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[8000] = Pow(fac[8000],mod - 2);
  for(int i = 7999;i >= 0;i --)
    inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
  return ;
}

const int base = 2001;

int C(int n , int m) {
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

signed main() {
	Pre();
	int n = gi();
	for(int i = 1;i <= n;++ i) a[i] = gi() , b[i] = gi();
	for(int i = 1;i <= n;++ i)  f[base - a[i]][base - b[i]] ++;
	for(int i = 1;i <= 4000 + 4;++ i) {
		for(int j = 1;j <= 4000 + 4;++ j) {
			f[i][j] += f[i - 1][j] + f[i][j - 1];
			f[i][j] %= mod;
		}
	}
	int Ans = 0;
	for(int i = 1;i <= n;++ i) {
		Ans += f[a[i] + base][b[i] + base] ;
		Ans %= mod;
		Ans -= C(2 * a[i] + 2 * b[i] , 2 * a[i]);
		Ans %= mod;
	}
	Ans += mod;
	Ans %= mod;
	Ans = Ans * inv2 % mod;
	std::cout << Ans;
	return 0;
}

Measured memory_bytes: 130432
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    if(s[0]==s[2])yes;
    else no;
}


Measured memory_bytes: 3652
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
  
n=int(input())
a=list(map(int,input().split()))
s=1
for i in a:
  s=lcm(s,i)
ans=0
for i in a:
  ans+=s//i
print(ans % 1000000007)

Measured memory_bytes: 6112
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
b = [int(input()) for i in range(m)]

for i in range(len(a)):
    ans = 0
    for j in range(len(b)):
        ans += a[i][j] * b[j]
    print(ans)


Measured memory_bytes: 6020
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 10005
typedef long long ll;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
ll n,k,a[N],sum,x;
ll f[N],cnt=0,p[N],pn;
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		sum+=a[i];
	}
	for(int i=1;i*i<=sum;i++){
		if(sum%i==0){
			f[++cnt]=i;
			if(i*i!=sum)f[++cnt]=sum/i;
		}
	}
	sort(f+1,f+cnt+1);
	for(int i=cnt;i>=1;i--){
		ll t=f[i],tot=0,o=0;
		for(int j=1;j<=n;j++){
			p[j]=a[j]%t;
			tot+=t-p[j];
		}
		if(tot==0){
			cout<<t<<endl;
			return 0;
		}
		sort(p+1,p+n+1);
		for(int j=1;j<=n;j++){
			o+=p[j];
			tot-=t-p[j];
			if(o==tot)break;
		}
		if(o<=k){
			cout<<t<<endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main()
{
  int d;
  cin >> d;
  
  cout << "Christmas";
  if (d <= 24) cout << " Eve";
  if (d <= 23) cout << " Eve";
  if (d <= 22) cout << " Eve";
  cout << endl;
}

Measured memory_bytes: 256
object Main extends App {
  var n = scala.io.StdIn.readInt()
  var s = scala.io.StdIn.readLine()
  val inputArray =  s.split(" ").map(_.toInt)
  val max = inputArray.max
  val sumExceptMax = inputArray.sum - max
  if (max < sumExceptMax) {
    println("Yes")
  } else {
    println("No")
  }
}


Measured memory_bytes: 25536
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C;
  cin>>A>>B>>C;
  bool flag=false;
  if(A==B&&A!=C){
    flag=true;
  }
  if(A==C&&C!=B){
    flag=true;
  }
  if(B==C&&A!=C){
    flag=true;
  }
  if(flag){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

    

Measured memory_bytes: 256
#include<stdio.h>
 
int len(char *s){
  int len;
  len = 0;
  while(s[len]){
    len++;
  }
  
  return len;
}
 
int main(){
  char a[11], b[11], c[11];
  int alen, blen, clen;
  scanf("%s %s %s", a, b, c);
  
  alen = len(a);
  blen = len(b);
  clen = len(c);
  
  if(a[alen - 1] == b[0] && b[blen - 1] == c[0]){
    printf("YES\n");
  } else {
    printf("NO\n");
  }
  
  return 0;
}

Measured memory_bytes: 128
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def check(h):
    n = len(h)
    cps = [False]*n
    for i in range(n):
        if h[i] != i+1:
            cps[i] = True
    return cps
        

def main():
    n = int(input())
    Ps = list(map(int, input().split()))
    cnt = int()
    #となりあうFalseは絶対にTrueになる
    cps = check(Ps)
    for i in range(n):
        if not cps[i]:
            if i == n-1:
                cps[i], cps[i-1] = cps[i-1], cps[i]
            else:
                cps[i], cps[i+1] = True, True
            cnt += 1
    eprint(cps)
    print(cnt)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 94080
N, M = [int(_) for _ in input().split()]
AB = [tuple(int(_) for _ in input().split()) for i in range(M)]

AB.sort()

result = 1

x1, x2 = 1, N
for a, b in AB:
    # print(x1, x2, a, b)
    if x2 <= a:
        # print("*")
        result += 1
        x1, x2 = a, b
    else:
        x1 = max(x1, a)
        x2 = min(x2, b)

print(result)



Measured memory_bytes: 17000
#include <bits/stdc++.h>
using namespace std;

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 60;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};


int main()
{
  int n, m; cin >> n >> m;
  for(ll i = m/n;; --i) if(m%i==0) {
    cout << i << endl;
    return 0;
  }
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#include<cstdlib>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
typedef long long ll;

int main(){
  string s;
  cin >> s;

  ll k;
  cin >> k;

  int n = s.size();
  
  int a=0;
  rep(i,n-1){
    if(s.at(i)==s.at(i+1)){a++; i++;}
  }
  int fi=1, la=1;
  rep(i,n-1){
    if(s.at(i)==s.at(i+1)) fi++;
    else break;
  }
  rep(i,n-1){
    if(s.at(n-1-i)==s.at(n-2-i)) la++;
    else break;
  }

  if(fi==n){
    ll p = n*k/2;
    cout << p;
    return 0;
  }
  
  int b=0;
  if(s.at(0)==s.at(n-1)&&fi%2==1&&la%2==1) b=1;
  

  ll ans = k*a + (k-1)*b;
  cout << ans;
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>

using namespace std;
int main(){
int a[3];
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);
if(a[0]==a[1]&&a[2]!=a[0]||a[2]==a[1]&&a[1]!=a[0])
{
  cout<<"Yes"<<endl;
}
else{
  cout<<"No"<<endl;
}


return 0;}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000000)
from collections import deque 
INF = int(1e9)
ans = INF
def main():
    N, M, X = map(int, readline().split())
    costs = []
    score = []
    for _ in range(N):
        c, *d = map(int, readline().split())
        costs.append(c)
        score.append([i for i in d])
    dq = deque()
    def dfs():
        global ans
        if len(dq) == N:
            cost = 0
            sumScore = [0 for _ in range(M)]
            for i in range(N):
                if dq[i]:
                    cost += costs[i]
                    for j in range(M):
                        sumScore[j] += score[i][j]
            flag = True 
            for i in range(M):
                if sumScore[i] < X: 
                    flag = False

            if flag:
                ans = min(ans, cost)
                return 
            return 
        for i in range(2): 
            dq.append(i)
            dfs()
            dq.pop()

    dfs()
    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 9556
#include <stdio.h>
#include <string.h>

int substr(char *t,const char *s,int pos,int len){
    if(pos < 0||len < 0||len > strlen(s))
        return -1;
    for(s += pos;*s!='\0' && len>0;len--)
        *t++ = *s++;
    *t = '\0';
    return 0;
}


int main(void) {
    int  N;
    char S[128];
    char S1[128];
    char S2[128];

    scanf("%d",&N);
    scanf("%s",&S);

    if(N%2 == 0){
		substr(S1,S,0,N/2);
        substr(S2,S,N/2,N/2);

        if(strcmp(S1,S2)==0){
            printf("Yes");
        }
      	
      	else{
          	printf("No");
        }
    }

    else{
        printf("No");
    }

    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>

#define FOR_N(n) for(int i=0;i<n;i++)
#define P_INT(d) printf("%d\n", d);
#define P_DOUBLE(lf) printf("%lf\n", lf);
#define P_STR(s) printf("%s\n", s);
#define INF 2147483647

using namespace std;
     
main(){
    int n,l;
    cin >> n >> l;
    
    vector<string> s;
    string buff;
    getline(cin, buff);
    FOR_N(n){
        getline(cin, buff);
        s.push_back(buff);
    }
    sort(s.begin(), s.end());
    FOR_N(n){
        cout << s[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	char a[10000];
	int b=0,c=0,d=0;
	cin>>a;
	b=strlen(a);
	for(int i=0;i<b;i++){
		if(a[i]=='C'){
			c=1; 
		}
		if(a[i]=='F'&&c==1){
			d=1;
		}
	}
	if(c>0&&d>0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define rep(i,N) repv(i,0,N)
#define reps(i,N) repvs(i,0,N)
#define repv(i,a,b) for(int i=a;i<b;i++)
#define repvs(i,a,b) for(int i=a+1;i<=b;i++)
#define repr(i,N) for(int i=N-1;i>=0;i--)
#define reprs(i,N) for(int i=N;i>0;i--)

#define d(a) if(isDebugMode) cout<<#a<<"="<<a<<","
#define d2(a,b) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b
#define d3(a,b,c) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c
#define d4(a,b,c,d) if(isDebugMode) cout<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<","<<#d<<"="<<d
#define da(arr,N){if(isDebugMode){rep(i,N+1){if(arr[i]==INF)printf("INF ");else cout<<arr[i]<<" ";} cout<<endl;}}
#define da2(arr,N,M){if(isDebugMode)rep(i,N+1){rep(j,M+1){if(arr[i][j]==INF)printf(" INF");else printf(" %3d",arr[i][j]);}cout<<endl;}}
#define pb push_back
#define pob pop_back
#define s(a) cout<<a<<endl;

auto chmax =[](int &a,int b){ a = max(a, b);};
auto chmin =[](int &a,int b){ a = min(a, b);};

typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
const int MOD = 1000000007;
const int dx[4] = { 0, 1, 0,-1};
const int dy[4] = { 1, 0,-1, 0};

bool isDebugMode=1;
//--------------------------------------//
int n;
int a[100000];
int b[100001];
int d[100001];
ll ans;
void solve(){
	sort(a,a+n);
	int c=1;
	rep(i,n){
		b[c]=a[i];
		c+=2;
		if(c>=n)break;
	}
	c=2;
	reps(i,n){
		b[c]=a[n-i];
		c+=2;
		if(c>=n)break;
	}
	c=2;
	rep(i,n){
		d[c]=a[i];
		c+=2;
		if(c>=n)break;
	}
	c=1;
	reps(i,n){
		d[c]=a[n-i];
		c+=2;
		if(c>=n)break;
	}
	b[0]=d[0]=a[n/2];
	b[n]=d[n]=a[n/2];
	ll m1=0;
	rep(i,n-1){
		ans+=abs(b[i+1]-b[i]);
		m1+=abs(d[i+1]-d[i]);
	}
	ans=max(ans,m1);
	ll m=0;
	m1=0;
	reps(i,n-1){
		m+=abs(b[i+1]-b[i]);
		m1+=abs(d[i+1]-d[i]);
	}
	ans=max(max(ans,m),m1);
	cout<<ans<<endl;
}

int main(){
	cin>>n;
	rep(i,n) {
		cin>>a[i];
	}
	solve();
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=1e6+5;

int32_t main()
{
	IOS;
	int n, h, w;
	cin>>n>>h>>w;
	int ans=(n-h+1)*(n-w+1);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX_LIST 105000

int main(){
	bool prime[MAX_LIST];
	for(int i=0;i<MAX_LIST;i++){
		prime[i]=1;
	}
	prime[0]=prime[1]=0;
	for(int i=0;i*i<MAX_LIST;i++){
		if(prime[i]==1){
			for(int j=i*2;j<MAX_LIST;j=j+i){
				prime[j]=0;
			}
		}
	}
	int primelist[10000];
	int j=0;
	for(int i=0;i<MAX_LIST;i++){
		if(prime[i]==1){
			primelist[j]=i;
			j++;
			if(j>10000-1){
				break;
			}
		}
	}
	int ans;
	while(cin>>j,j){
		ans=0;
		for(int i=0;i<j;i++){
			ans=ans+primelist[i];
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1300
#include<iostream>
using namespace std;

int main(void) {
	int a[4];
	int b[4];

	while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {

		int hit=0, blow=0;
		
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				if(a[i]==b[j]){
					if(i==j) hit++;
					else blow++;
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
using ll = long long;
using ld =long double;
//#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<int,pii> piii;
signed main(){
    int n; cin>>n;
    string s; cin>>s;
    vector<bool>used(s.size(),true);
    rep(i,s.size()){
        if(used[i]==false)continue;
        for(int j=i+1;j<s.size();j++){
            if(s[i]==s[j]||used[j]==false)continue;
            else if((s[i]=='('&&s[j]==')')){
                used[i]=used[j]=false;
                break;
            }
            
        }
    }
    string ans=s;;
    rep(i,s.size()){
        if(s[i]=='('&&used[i])ans.push_back(')');
        if(s[i]==')'&&used[i]){string t="(";t+=ans; ans=t;}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int w[300];
int dp[310][310];

int main(){
    int n;
    while(cin >> n, n){
        for(int i = 0; i < n; i++) cin >> w[i];
        memset(dp, 0, sizeof dp);

        for(int len = 2; len <= n; len++){
            for(int l = 0; l + len <= n; l++){
                for(int c = l + 1; c < l + len; c++){
                    dp[l][l + len] = max(dp[l][l + len], dp[l][c] + dp[c][l + len]);
                }
                if(abs(w[l] - w[l + len - 1]) <= 1 && dp[l + 1][l + len - 1] == len - 2){
                    dp[l][l + len] = len;
                }
                //printf("[%d, %d) = %d\n", l, l + len, dp[l][len] );
            }
        }

        cout << dp[0][n] << endl;
    }

}

Measured memory_bytes: 3496
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 62;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int h, w;
vector<string> s;
int memo[110][110];
int rec(int i, int j){
    //cout << i << " " << j << endl;
    if(i == 0 && j == 0){
        return 0;
    }
    if(memo[i][j] != -1) return memo[i][j];
    int res = 1e9;
    int f = 0;
    if(i > 0) f = (s[i][j] == '.' && s[i - 1][j] == '#');
    if(i > 0) res = min(res, rec(i - 1, j) + f);
    if(j > 0) f = (s[i][j] == '.' && s[i][j - 1] == '#');
    if(j > 0) res = min(res, rec(i, j - 1) + f);

    if(i == h - 1 && j == w - 1){
        if(s[i][j] == '#') res++;
    }

    return memo[i][j] = res;
}
int main(void){
    cin >> h >> w;
    s.resize(h);
    rep(i, h){
        cin >> s[i];
    }

    rep(i,110){
        rep(j, 110){
            memo[i][j] = -1;
        }
    }

    cout << rec(h - 1, w - 1) << endl;
}

Measured memory_bytes: 384
#include<cstdio>
int h,w,n,a[20000],c[200][200];
int main()
{
	scanf("%d%d%d",&h,&w,&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1,color=1;i<=h;i++)
		if(i&1)for(int j=1;j<=w;j++)
		{
			c[i][j]=color;
			if(!--a[color])color++;
		}
		else for(int j=w;j>0;j--)
		{
			c[i][j]=color;
			if(!--a[color])color++;
		}
	for(int i=1;i<=h;i++,puts(""))
		for(int j=1;j<=w;j++)printf("%d ",c[i][j]);
	return 0;
}


Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main(){
  int n; cin >> n;
  int adj[n+1][n+1];
  for(int i=1;i<=n;i++){
    int u,k; cin >> u >> k;
    for(int i=1;i<=n;i++) adj[u][i]=0;
    for(int i=0;i<k;i++){
      int v; cin >> v;
      adj[u][v]=1;
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(j-1) cout << " " << adj[i][j];
      else cout << adj[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
int n, cnt[N][2];
string s;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // R = 1
    // W = 0
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R'){
            cnt[i + 1][1] = cnt[i][1] + 1;
            cnt[i + 1][0] = cnt[i][0];
        } else {
            cnt[i + 1][1] = cnt[i][1];
            cnt[i + 1][0] = cnt[i][0] + 1;
        }
    }

    //goal -> 111110000
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'R'){
            ans++;
        }
    }

    for(int i = 1; i <= n; i++){
        int cnt0 = cnt[i][0];
        int cnt1after = cnt[n][1] - cnt[i][1];
        int ans1 = cnt0 + cnt1after - min(cnt0, cnt1after);
        ans = min(ans, ans1);
    }

    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 5332
#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned int
using namespace std;
inline int read(){
	int s=0,t=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*t;
}
const int N=105;
int n,m,K,P;
int C[N][N],p[N][N],f[2][N][N];
inline int Mod(int x){return x>=P?x-P:x;}
void Pre(int n){
	for(int i=0;i<=n;i++){
		C[i][0]=p[i][0]=1;
		for(int j=1;j<=n;j++)p[i][j]=1ll*p[i][j-1]*i%P;
		for(int j=1;j<=i;j++)C[i][j]=Mod(C[i-1][j-1]+C[i-1][j]);
	}
}
void Clear(int t){
	for(int i=0;i<=n;i++)
	for(int j=0;j<=m;j++)f[t][i][j]=0;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),K=read(),P=read(),Pre(100);
	int o=0;f[0][0][0]=1;
	for(int t=1;t<=K;t++){
		o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*p[K-t+1][j]*p[t][m-j]%P,y=f[o^1][i][j];
			for(int a=0;a+i<=n;a++,y=1ll*y*x%P)f[o][i+a][j]=Mod(f[o][i+a][j]+1ll*C[n-i][a]*y%P);
		}o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*p[K-t+1][i]*p[t][n-i]%P,y=f[o^1][i][j];
			for(int b=0;b+j<=m;b++,y=1ll*y*x%P)f[o][i][j+b]=Mod(f[o][i][j+b]+1ll*C[m-j][b]*y%P);
		}o^=1,Clear(o);
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*(P-p[K-t][j])*p[t][m-j]%P,y=f[o^1][i][j];
			for(int a=0;a+i<=n;a++,y=1ll*y*x%P)f[o][i+a][j]=Mod(f[o][i+a][j]+1ll*C[n-i][a]*y%P);
		}o^=1,Clear(o);	
		for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(f[o^1][i][j]){
			int x=1ll*(P-p[K-t][i])*p[t][n-i]%P,y=f[o^1][i][j];
			for(int b=0;b+j<=m;b++,y=1ll*y*x%P)f[o][i][j+b]=Mod(f[o][i][j+b]+1ll*C[m-j][b]*y%P);
		}
	}printf("%d",f[o][n][m]);
	return 0;
}
/*2 2 2 998244353*/


Measured memory_bytes: 3928
#include <bits/stdc++.h>

using namespace std;

#define rep(i, x)   for (__typeof(x) i = 0; i < x; i++)
#define mp             make_pair
#define pb             push_back
#define fi             first
#define se             second
#define sz(x)          (int)((x).size())
#define all(x)         (x).begin(), (x).end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define eprintf(...)   fprintf(stderr, __VA_ARGS__)
#define debug(x)       { cerr << #x << " = " << x << endl; }
#define repi(i, x)  for (__typeof(x) i = x-1; i >= 0; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
typedef long long      ll;
typedef pair<int, int> ii;
typedef pair<ii, int>  iii;
typedef vector<int>    vi;
typedef vector<ii>     vii;
typedef vector<iii>    viii;
typedef vector<vector<int> > vvi;
const   int            infi = numeric_limits<int>::max();
const   double         eps = 0;
const   int            ms  = 0;

int main()
{
    int L, l;
    cin >> L;
    vi ar;
    int L_ = L;
    if(L==2){
        cout << 2 << " " << 2 << endl;
        cout << 1 << " " << 2 << " " << 0 << endl;
        cout << 1 << " " << 2 << " " << 1 << endl;
        return 0;
    }
    while(L > 0){
        l = L;
        int a = 0;
        int b = 1;
        for(;b <= l && a <= 19 ;a++){
            b*=2;
        }
        
        L-=b/2;
        a--;
        
        debug(a);
        debug(b);
        ar.push_back(a);
    }
    int N = ar[0] + 1;

    cout << N << " " << 2*ar[0]  +ar.size()-1<< endl;
    
    
   
    
    int b = 1;
    for(int i = 1; i <= ar[0]; i++){
        cout << i << " " << i+1 << " " << 0 << endl; 
        cout << i <<" " << i+1 << " " << b << endl;;
        b*=2;
    }
    int c = b;
    for(int i = 1; i < ar.size(); i++){
        cout << ar[i]+1 << " " << N <<" " << c << endl;
        c+=pow(2, ar[i]);
    }
    for(int i = 0; i < L; i++)
    cout << 1  << " " << N << " " <<  L_-i-1 << endl;

    return 0;
}

Measured memory_bytes: 384