akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    vector<pint> v(n);
    REP(i, n) { cin >> v[i].second >> v[i].first; }
    lint ans=0;
    lint t=0;
    sort(ALL(v));

    REP(i,n){
        t += v[i].second;
        if(t>v[i].first){
            cout << "No"<< "\n";
            return 0;
        }
    }

    cout << "Yes" <<"\n";

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
  int N;
  std::cin >> N;

  std::map<std::string, std::map<int, int>> SP;

  for (int i = 0; i < N; ++i) {
    std::string s;
    int p;
    std::cin >> s >> p;
    auto find = SP.find(s);
    if (find != SP.end()) {
      find->second.insert(std::make_pair(p, i + 1));
    } else {
      std::map<int, int> pm;
      pm.insert(std::make_pair(p, i + 1));
      SP.insert(std::make_pair(s, pm));
    }
  }

  for (auto &sp : SP) {
    for (auto iter = sp.second.rbegin(); iter != sp.second.rend(); ++iter) {
      std::cout << iter->second << std::endl;
    }
  }

  return 0;
}

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int H, W;
    cin >> H >> W;
    char A[H][W];
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            cin >> A[h][w];
        }
    }

    int dy[4] = { 0, 1, 0, -1 };
    int dx[4] = { 1, 0, -1, 0 };

    int length = H + W - 1;
    pair<int, int> next = { 0, 0};

    if (A[0][0] == '.') {
        cout << "Impossible" << '\n';
        return 0;
    }
    while (--length) {
        int y = next.first;
        int x = next.second;

        int path = 0;
        for (int i = 0; i <= 1; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx < W && ny < H && A[ny][nx] == '#') {
                path++;
                next = make_pair(ny, nx);
                A[y][x] = '.';
            }
        }
        if (path == 0 || path == 2) {
            cout << "Impossible" << '\n';
            return 0;
        }

        for (int i = 2; i <= 3; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx < W && ny < H && A[ny][nx] == '#') {
                cout << "Impossible" << '\n';
                return 0;
            }
        }
    }
    A[H - 1][W - 1] = '.';

    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            if (A[h][w] == '#') {
                cout << "Impossible" << '\n';
                return 0;
            }
        }
    }

    cout << "Possible" << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MOD 1000000007
using namespace std;
typedef pair<int,int> P;

int n, V;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<int> G[100000];
vector<int> rG[100000];
vector<int> vs;
bool used[100000];
int cmp[100000];
map<P,int> m;
map<P,int>::iterator it;

void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v){
	used[v] = true;
	rep(i,G[v].size()){
		if(!used[G[v][i]]) dfs(G[v][i]);
	}
	vs.push_back(v);
}

void rdfs(int v, int k){
	used[v] = true;
	cmp[v] = k;
	rep(i,rG[v].size()){
		if(!used[rG[v][i]]) rdfs(rG[v][i], k);
	}
}

int scc(){
	memset(used,0,sizeof(used));
	vs.clear();
	rep(v,V){
		if(!used[v]) dfs(v);
	}
	memset(used,0,sizeof(used));
	int k = 0;
	for(int i = vs.size()-1; i >= 0; i--){
		if(!used[vs[i]]) rdfs(vs[i],k++);
	}
	return k;
}

void init(){
	m.clear();
	rep(i,100000){
		G[i].clear();
		rG[i].clear();
		used[i] = false;
		cmp[i] = 0;
	}
	vs.clear();
}

void solve(){
	init();
	V = n*4;
	rep(i,n){
		int x, y; char d;
		cin >> x >> y >> d;
		m[P(x,y)] = i+1;
		if(d == 'x') m[P(x+1,y)] = i+n+1;
		else m[P(x,y+1)] = i+n+1;
	}
	for(it = m.begin(); it != m.end(); it++){
		if(it->second == 0) continue;
		int id1 = it->second-1;
		P p = it->first;
		rep(i,4){
			if(m[P(p.first+dx[i],p.second+dy[i])] != 0){
				int id2 = m[P(p.first+dx[i],p.second+dy[i])]-1;
				if(abs(id2-id1) == n){
					add_edge(id1,id2+n*2);
					add_edge(id2,id1+n*2);
					add_edge(id1+n*2,id2);
					add_edge(id2+n*2,id1);
				} else{
					add_edge(id1,id2);
					add_edge(id2,id1);
					add_edge(id1+n*2,id2+n*2);
					add_edge(id2+n*2,id1+n*2);
				}
			}
		}
	}
	scc();
	
	rep(i,2*n){
		if(cmp[i] == cmp[i+2*n]){
			puts("No");
			return;
		}
	}
	puts("Yes");
}

int main(){
	while(true){
		cin >> n;
		if(n == 0) break;
		solve();
	}
}

Measured memory_bytes: 22656
#include <iostream>
using namespace std;
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string>
#include <cstdlib>

int Board[100][100] = {};
int dx[8] = {1, 2, 1, 2, -1, -2, -1, -2}, dy[8] = {2, 1, -2, -1, -2, -1, 2, 1};

int main() {
	string A, B, C; cin >> A >> B >> C;
	int a = 0, b = 0, c = 0;
	char turn = 'a';
	while(1) {
		if(a == A.length()+1 ) { cout << "A" << endl; break; }
		if(b == B.length()+1 ) { cout << "B" << endl; break; }
		if(c == C.length()+1 ) { cout << "C" << endl; break; }

		if(turn == 'a') { turn = A[a]; a++;}
		else if(turn == 'b') { turn = B[b]; b++;}
		else { turn = C[c]; c++;}
	}
	return 0;
}

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

void solve(long long X, long long A, long long B){
    cout << (X - A) % B << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long X;
    scanf("%lld",&X);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(X, A, B);
    return 0;
}


Measured memory_bytes: 256
# editorial
N = int(input())

#from functools import lru_cache
#@lru_cache(maxsize=1000)
def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if  all(s.count(c) for c in "753") else 0
    for c in "753": #文字列数値をforで回すときの書き方！ 覚える
        ret += dfs(s+c) #pythonなのでそのまま+できる
    return ret

print(dfs("0"))

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

using namespace std;

int main(){
    double N, T, A, h;
    vector<double> Hs;

    cin >> N >> T >> A;
    double anstemp = 10000000;
    int ans;
    for(int i = 0; i < N; i++){
        cin >> h;
        h = T - h*0.006;
        if(abs(A - h) < anstemp){
            anstemp = abs(A-h);
            ans = i;
        }
    }

    cout << ans+1 << endl;



    return 0;
}

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

int main(){
        bool check=true;
        int w, h, at_x, at_y;

        while(1){
                int total=1;
                char tile[22][22] = { { 0 } };
                scanf("%d %d", &w, &h);
                if( w == 0 && h == 0 ) break;
                for( int i=0; i<h; i++ ){
                        scanf("%s", &tile[i+1][1]);
                }
                check = true;
                while( check ){
                        check = false;
                        for( int y=1; y<=h; y++){
                                for( int x=1; x<=w; x++ ){
                                        if( tile[y][x] == '@' ){
                                                at_x = x;
                                                at_y = y;
                                                if( tile[y-1][x] == '.' ){
                                                        tile[y-1][x] = '@';
                                                        check = true;
                                                        total++;
                                                }
                                                if( tile[y+1][x] == '.' ){
                                                        tile[y+1][x] = '@';
                                                        check = true;
                                                        total++;
                                                }
                                                if( tile[y][x-1] == '.' ){
                                                        tile[y][x-1] = '@';
                                                        check = true;
                                                        total++;
                                                }
                                                if( tile[y][x+1] == '.' ){
                                                        tile[y][x+1] = '@';
                                                        check = true;
                                                        total++;
                                                }
                                        }
                                }
                        }
                }
                printf("%d\n", total);
        }
        return 0;
}

Measured memory_bytes: 1032
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int h,w,a,b;
	bool can=true;
	cin >>h>>w>>a>>b;
	if(b>=h or a>=w){
		can=false;
	}
	
	vector<pair<int,int>>range(2,mp(0,0));
	VVi ans(h,Vi(w,0));

	if(can){
		for(int i=0;i<b;i++){
			for(int j=0;j<a;j++){
				ans[i][j]=1;
			}
		}
		for(int i=b;i<h;i++){
			for(int j=a;j<w;j++){
				ans[i][j]=1;
			}
		}
		rep(i,h){
			rep(j,w){
			cout<<ans[i][j];
		
		}
		cout<<endl;
		}

	

	}
	else{
		cout<<"No"<<endl;
	}
	
}

Measured memory_bytes: 7548
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main(){
    int H,W;
    while(true){
        scanf("%d %d",&H,&W);
        if(H == 0 && W == 0) break;
        for(int i = 0; i < W; i++) printf("#");
        printf("\n");
 
        for(int i = 1; i < H-1; i++){
            printf("#");
            for(int j = 1; j < W-1; j++) printf(".");
            printf("#\n");
        }
 
        if(H > 1){
            for(int i = 0; i < W; i++) printf("#");
            printf("\n");
        }
        printf("\n");
    }
}


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

int main(){
  int N ;
  cin >> N ;
  vector<int> p(N) ;
  vector<int> q(N) ;
  vector<int> original(N) ;
  for(int i=0;i<N;i++) {
    original[i]= i+1 ;
  }
  int count =0;
  int a =0;
  int b =0;
  for(int i=0;i<N;i++){
    cin >> p[i] ;
  }
  for(int j=0;j<N;j++){
    cin >> q[j] ;
  }
  
  do{
    count++;
    if(original==p) a = count;
    if(original==q) b = count;
  }
    while(next_permutation(original.begin(),original.end()));
  
  
  cout << abs(a-b) << endl;
}



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

int main(){
  int n, b[2]={0};
  cin >> n;
  while(n--){
    string s;
    cin >> s;
    for(int i=0; i<s.length(); i++){
      if(s[i]=='0'){
	if(b[0] != 0){
	  int a = b[0]-'0';
	  if(a==1){
	    b[1]%=5;
	    if(b[1]==0)
	      cout << " ";
	    else if(b[1]==1)
	      cout << ".";
	    else if(b[1]==2)
	      cout << ",";
	    else if(b[1]==3)
	      cout << "!";
	    else if(b[1]==4)
	      cout << "?";
	  }
	  else if(a==2 || a==3 || a==4 || a==5 || a==6 || a==8){
	    b[1]%=3;
	    if(b[1]==0)
	      b[1] = 3;
	    if(a==8)
	      b[1]++;
	    char c = b[1]+'a'-1+3*(b[0]-'0'-2);
	    cout << c;
	  }
	  else if(a==7 || a==9){
	    b[1]%=4;
	    if(b[1]==0)
	      b[1] = 4;
	    if(a==9)
	      b[1]++;
	    char c = b[1]+'a'-1+3*(b[0]-'0'-2);
	    cout << c;
	  }
	}
	b[0]=0;
	b[1]=0;
      }
      else{
	b[0] = s[i];
	b[1]++;
      }
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  long long int N;
  long long int A;
  long long int B;
  long long int sum = 0;
  long long int num = 0;
  cin>>N;
  cin>>A;
  cin>>B;
  num = N % (A + B);
  sum += ((N / (A + B)) * A) + (min(num,A));
  cout<<sum<<'\n';
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3

int main(){
    cin.sync_with_stdio(false);
    string s;
    cin >> s;
    cout << s[0] << s.size() - 2 << s[s.size() - 1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}

int f(int x){
    if(x==3) return 100000;
    if(x==2) return 200000;
    if(x==1) return 300000;
    else return 0;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x,y;cin>>x>>y;
    int ans = f(x) + f(y);
    if(x==1 && y==1) ans+=400000;
    cout<<ans<<endl;
}
// ddcc2020_qual_a

Measured memory_bytes: 256
n,w=map(int,input().split())
dp=[[100000000001]*100001for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  a,b=map(int,input().split())
  for j in range(100001):
    if j>=b:dp[i][j]=min(dp[i-1][j],dp[i-1][j-b]+a)
    else:dp[i][j]=dp[i-1][j]
i=10**5
while dp[n][i]>w:i-=1
print(i)

Measured memory_bytes: 119788
#include <iostream>

using namespace std;

int main()
{
	int a,b,c,d;
	
	cin >> a;
	if(a >= 3600)
	{
		b = a / 3600;
		a = a % 3600;
	}
	if(a >= 60)
	{
		c = a / 60;
		a = a % 60;
	}
	d = a;
	cout << b << ":" << c << ":" << d << endl;
	
}

Measured memory_bytes: 1168
#include <iostream>
#include <algorithm>
#include <string> 
#include <math.h>
#include <vector>
#define rep(i,n) for(int i=0; i< int(n); i++)
using namespace std;



int main(){
	int k,s;
	cin >> k >> s; 
	int res = 0;
	for(int x=0; x<=k; x++){
		for(int y=0; y <= k; y++){
			int z = s - x - y;
			if(0 <= z and z <= k){
				res += 1;
			}
		}
	}
	cout << res << endl;

} 



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#define REP(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int main()
{
    int N;
    int d[60];
    cin >> N;
    REP(i, N) cin >> d[i];
    int ans = 0;
    REP(i, N){
        REP(j, i){
            ans += d[i] * d[j];
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define maxPN 100000
#define PNs  1000100
int countPN = 0, countPNs = 0;
int PrimeNum[maxPN], temp;
bool PN[PNs];

bool IsPrimeNumber(int x);

void PrimeN(){
	int i, j;
	PrimeNum[0] = 2;
	PN[2] = true;PrimeNum[countPN++] = 2;
	PN[3] = true;PrimeNum[countPN++] = 3;
//	PN[5] = true;PrimeNum[countPN++] = 5;
	
	for(i = 6; i  < PNs;i+=6){
		if(IsPrimeNumber(i-1)){
			PrimeNum[countPN++] = i-1;
			PN[i-1] = true;//cout<<i-1<<endl;
		}
		if(IsPrimeNumber(i+1)){
			PrimeNum[countPN++] = i+1;
			PN[i+1] = true;//cout<<i+1<<endl;
		}
		countPNs = i+1;//cout<<i-1<<" "<<PN[i-1]<<endl;
	}
}

bool IsPrimeNumber(int x){
	//if(x == 2 || x == 3) return true;
	//if(x <= 4 || x%2 == 0 || x%3 == 0)   return false;
	//if(x < countPNs) return PN[x];
	for(int i = 0; PrimeNum[i] * PrimeNum[i] <= x; i++)
		if(x%PrimeNum[i] == 0)return false;
	return true;
}


int main(){
//	clock_t start, end;
	int n = true, counta;
//	start = clock();
	PrimeN();
//	cout<<PrimeNum[countPN-1]<<" "<<countPNs<<endl;
//	cout<<clock()-start<<"ms"<<endl;
	
	while(cin>>n){
		counta = 1;
		
		
		//cout<<(IsPrimeNumber(n)?"yes":"no")<<endl;
	//	start = clock();
		//cout<<IsPrimeNumber(n)<<endl;
		for(int i = 1; i <= n; i+=2){
			if(PN[i])counta++;
		//	cout<<i<<" "<<PN[i]<<endl;
		}
		if(n == 1) counta = 0;
		cout<<counta<<endl;
	//	cout<<clock()-start<<"ms"<<endl;
	}
	return 0;
}


Measured memory_bytes: 4300
// -*- coding:utf-8-unix -*-

use proconio::input;
use rand::Rng;

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        ms - STIME
    }
}

fn calclate_score(D: usize, s: &Vec<Vec<isize>>, c: &Vec<isize>, out: &Vec<usize>) -> isize {
    let mut sat = 0;
    let mut last = vec![0; 26];
    for d in 0..D {
        assert!(0 <= out[d] && out[d] <= 25);
        let j = out[d as usize] as usize;
        last[j] = d + 1;
        for i in 0..26 as usize {
            sat -= (d + 1 - last[i]) as isize * c[i];
        }
        sat += s[d][j];
    }
    sat
}

fn main() {
    input! {
        D: usize,
        c: [isize; 26],
        s: [[isize; 26]; D],
    }
    let mut out = vec![0 as usize; D];
    for i in 0..D {
        let mut max = 0;
        for j in 0..26 {
            max = if s[i][max] < s[i][j] { j } else { max };
        }
        out[i] = max;
    }
    // let mut rng = rand::thread_rng();
    // let mut max_score = -1000000000;
    // while get_time() < 1.9 {
    //     let d: usize = rng.gen_range(0, D);
    //     let q: usize = rng.gen_range(0, 26);
    //     let old = out[d];
    //     out[d] = q;
    //     if max_score < calclate_score(D, &s, &c, &out) {
    //         max_score = calclate_score(D, &s, &c, &out);
    //     } else {
    //         out[d] = old;
    //     }
    // }
    for x in out {
        println!("{}", x + 1);
    }
    // eprintln!("{}", max_score);
}


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

int main(void){
    int n,k;
    cin >> n >> k;
    vector<int> num(n),a(n);
    for(int i = 0;i < n;i++){
        cin >> a[i];
        num[a[i]] += 1;
    }
    int sum = 0;
    sort(num.begin(),num.end(),greater<int>());
    for(int i = 0;i < k;i++){
        sum += num[i];
    }
    cout << n - sum << endl;
    
}

Measured memory_bytes: 1792
n = int(input())
a, b = map(int, input().split())
A = [int(i) for i in input().split()]
p1= 0
p2 = 0
p3 = 0

for i in range(n):
    if A[i] <= a:
        p1 += 1
    elif A[i] >= a + 1 and A[i] <= b:
        p2 += 1
    else:
        p3 += 1

print(min(p1, p2, p3))

Measured memory_bytes: 3064
#include <iostream>
#include <math.h>
#include <cstdio>

using namespace std;

double a, b, c, d, e, f;
double tmp_x, tmp_y, tmp;

int main()
{
	while (cin >> a >> b >> c >> d >> e >> f) {
		tmp_y = (d*c - a*f) / (d*b - a*e);
		tmp_x = (c - b*tmp_y) / a;
		printf("%.3f %.3f\n", tmp_x, tmp_y);
	}
	return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
typedef int int__;
#define int long long
#define pb push_back
#define pi pair<int,int>
#define vpi vector<pi>
#define vi vector<int>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define forn(i, n) for(int i = 0; i < int__(n); i++) 
#define sz(a) int__(a.size())
template<class A>ostream& operator<<(ostream& out,const vector<A>&v){out<<"[";forn(i,sz(v)){if(i)out<<", ";out<<v[i];}return out<<"]";}
const int MAX = 1e9 + 7;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int Mod(int x){const int mm=998244353;x%=mm;if(x<0)x+=mm;return x;}
int Pow(int x,int n){if(n==0)return 1;int t=Pow(x,n/2);t=Mod(t*t);if(n&1)t=Mod(t*x);return t;}
#define watch(x) cout << #x << " : " << x << endl;
int gcd(int x,int y){return y!=0 ? gcd(y,x%y) : x;}
 
int__ main() {
	fast;
	
	string a,b; cin >> a >> b;

	vvi dp(a.size() + 1, vi(b.size() + 1, 0));

	for(int i=1;i<=a.size();i++){
		for(int j=1;j<=b.size();j++) {
			if(a[i-1] == b[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
			else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}

	int times = dp[a.size()][b.size()];

	string ans = "";
	int x = a.size(),y = b.size();
	while(times > 0) {
		if(a[x-1] == b[y-1]) {
			ans += a[x-1];
			x--; y--;
			times--;
		}
		else {
			if(dp[x-1][y] > dp[x][y-1]) x--;
			else y--;
		}
	}

	reverse(ans.begin(), ans.end());

	cout << ans << endl;
}


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

typedef long long ll;
#define pa pair<int, int> 
#define pal pair<long long, long long>
#define pad pair<double, double>
#define pb push_back
#define mp make_pair
#define VIN(v) for(int64_t i=0;i<(v).size();i++){cin >> (v).at(i);}

typedef vector<bool> bvec;
typedef vector<int> ivec;
typedef vector<long long> lvec;
typedef vector<double> dvec;
typedef vector<pa> pvec;

typedef vector< vector<bool> > bmat;
typedef vector< vector<int> > imat;
typedef vector<string> svec;
typedef vector< vector<string> > smat;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll l, r;
    cin >> l >> r;
    int d = 2019;
    ll n = fmin(r-l, d);
    ll m = 2020;
    for (int i=0; i<n; i++) {
        for(int j=i; j<n; j++){
            ll ri = (l+i)%d;
            ll rj = (l+j+1)%d;
            ll rij = (ri*rj)%d;
            m = min(m, rij);
        }
    }
    cout << m << endl;
}


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

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<bool>>chk(h+2, vector<bool>(w+2, false));
  vector<vector<char>>a(h+2, vector<char>(w+2, '.'));
  for(int i=1; i<=h; i++)for(int j=1; j<=w; j++)cin >> a[i][j];
  int x=1, y=1;
  chk[x][y]=true;
  for(int i=0; i<h+w; i++){
    if(i%2==0)while(a[x+1][y]=='#'){x++; chk[x][y]=true;}
    if(i%2==0)while(a[x][y+1]=='#'){y++; chk[x][y]=true;}
  }
  if(!(x==h && y==w)){cout << "Impossible"; return 0;}
  for(int i=1; i<=h; i++)for(int j=1; j<=w; j++)if(a[i][j]=='#' && (!chk[i][j])){cout << "Impossible"; return 0;}
  cout << "Possible";
  return 0;
}

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

int main()
{
	int x, y; cin >> x >> y;
	vector<string>v(x);
	for (string& i : v) cin >> i;
	for (int i = 0 ; i < x ; ++i)
		for (int j = 0; j < y; ++j) 
			if (v[i][j] == '.') {
				int cnt = 0;
				if (j + 1 < y && v[i][j + 1] == '#') ++cnt;
				if (j - 1 >= 0 && v[i][j - 1] == '#') ++cnt;
				if (i + 1 < x && v[i + 1][j] == '#') ++cnt;
				if (i + 1 < x && j + 1 < y && v[i + 1][j + 1] == '#') ++cnt;
				if (i + 1 < x && j - 1 >= 0 && v[i + 1][j - 1] == '#') ++cnt;
				if (i - 1 >= 0 && v[i - 1][j] == '#') ++cnt;
				if (i - 1 >= 0 && j - 1 >= 0 && v[i - 1][j - 1] == '#') ++cnt;
				if (i - 1 >= 0 && j + 1 < y && v[i - 1][j + 1] == '#') ++cnt;
				v[i][j] = cnt + '0';
			}
	for (auto i : v) {
		for (auto j : i) cout << j;
		cout << "\n";
	}
	return 0;
}

// 

Measured memory_bytes: 3560
import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split())) for _ in range(q)]
l=list(range(1,m+1))
l=list(itertools.combinations_with_replacement(l,n))
ans=0
for i in l:
  kari=0
  for j in range(q):
    if i[abcd[j][1]-1]-i[abcd[j][0]-1]==abcd[j][2]:
      kari+=abcd[j][3]
  ans=max(ans,kari)
print(ans)

Measured memory_bytes: 21604
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        if(n.equals("Sunny")){
            System.out.println("Cloudy");
        }else if (n.equals("Cloudy")){
            System.out.println("Rainy");
        }else {
            System.out.println("Sunny");
        }



    }
}


Measured memory_bytes: 21076
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<int>Ps(N);
    for(int i=0; i<N; i++){
        cin >> Ps.at(i);
    }
    sort(Ps.begin(), Ps.end());
    int ans = 0;
    for(int i=0; i<N-1; i++)ans += Ps.at(i);
    ans += Ps.at(N-1)/2;
    cout << ans << endl;
}

Measured memory_bytes: 256
strs = gets.split("").map(&:chomp)
index = 1
ans = true

strs.each do |str|
    if index%2 == 0
        if str == 'R'
            ans = false
            break
        end
    else
        if str == 'L'
            ans = false
            break
        end
    end
    index += 1
end

if ans
    puts 'Yes'
else
    puts 'No'
end


Measured memory_bytes: 3836
import std.stdio;
import std.algorithm;
import std.range;

enum Size = 1260 - 540 + 1;

void main()
{
    uint N, M;
    while({readf("%s %s\n", &N, &M); return N;}())
    {
        uint[][] imos;
        foreach(i; 0 .. M)
            imos ~= new uint[Size];

        uint r;
        readf("%s\n", &r);
        foreach(i; 0 .. r){
            uint t, n, m, s;
            readf("%s %s %s %s\n", &t, &n, &m, &s);
            imos[m-1][t-540] += s ? 1 : -1;
        }

        foreach(i; 0 .. M){
            uint sum = 0;
            foreach(ref e; imos[i]){
                sum += e;
                e = sum;
            }
        }

        uint q;
        readf("%s\n", &q);
        foreach(i; 0 .. q){
            uint ts, te, m;
            readf("%s %s %s\n", &ts, &te, &m);
            imos[m-1][ts-540 .. te-540].filter!"a".walkLength().writeln;
        }
    }
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 61)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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; }



string s;
void solve(){
	cin >> s;
	int n = s.size();
	
	for(int i = 0; i < n; i++){
		if(s[i] == '?') cout << 'D';
		else cout << s[i];
	}
	cout << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

#define FOR(i, n) for(int i = 0; i < n; i++) 

#define pow CHANGETHENAMESTUPID

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

using ll = long long;
ll modinv(ll a, ll m) {
	assert(m > 0);
	if (m == 1) return 0;
	a %= m;
	if (a < 0) a += m;
	assert(a != 0);
	if (a == 1) return 1;
	return m - modinv(m, a) * m / a;
}
 
template <int MOD_> struct modnum {
private:
	int v;
public:
	static const int MOD = MOD_;
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
 
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
 
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
 
using num = modnum<int(1e9) + 7>;

void load() {
	int n, k; scanf("%d%d", &n, &k);
	int arr[n]; FOR(i, n) scanf("%d", arr + i);
	sort(arr, arr + n);
	num facts[n+1];
	facts[0] = num(1);
	for (int i = 1; i <= n; i++) facts[i] = facts[i-1] * num(i);
	num sumd(0), sump(0);
	auto choose = [&](int x, int y) {
		return facts[x] / facts[y] / facts[x-y];
	};
	FOR(i, n) {
		if (k - 1 > n - i - 1) continue;
		sumd += choose(n-i-1, k-1) * num(arr[i]);
	}
	for (int i = n-1; i >= 0; i--) {
		if (k-1 > i) continue;
		sump += choose(i, k-1) * num(arr[i]);
	}
	//printf("%d %d\n%d\n", (int)sumd, (int)sump, (int)(sump - sumd));
	printf("%d\n", (int)(sump - sumd));
}

void solve() {

}

int main() {
	load();
	solve();
	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>

using namespace std;
using ll = long long int; 


ll keta(ll a){
  ll ans = 1;
  while(1){
    if(a/10 > 0){
      ans++;
      a = a/10;
    }
    if(a<10) break;
  }
  return ans;
}


int main(void){

  ll n;
  cin>>n;
  ll sum = 0;
  ll piv;

  for(int i=1;i<=n;i++){
    sum += i;
    //cout<<sum<<endl;
    if(sum > n){
       piv = i;
       break;
    }else if(sum==n){
      piv = -1;
    }
  }

  if(piv == -1){
    sum = 0;
    int i=1;
    while(1){
      sum += i;
      cout<<i<<endl;
      if(i==n) return 0;
      
    }
  }
  for(int i=1;i<=piv;i++){
    if(i!=(sum - n)) cout<<i<<endl;
  }
    return 0;
}

Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

list = [a, b, c, d, e]

n = 10
x = []

for row in list:
    x.append((row + (n - row % n) % n) - row)

x.sort()

print(sum(x[:4]) + a + b + c + d + e)


Measured memory_bytes: 3060
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;
const ld PI = 3.14159265358979323846;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//



int main() {

    ll N; cin >> N;
    ll ans = 0;
    for (ll i = 1; i*i <= N; ++i) {
        ans = max(ans, i*i);
    }


    out(ans);
    

    return 0;
}









Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll choose2(ll s) {
  return s * (s - 1) / 2;
}

int main() {
  int n;
  cin >> n;
  vector<int> list(n);
  for (int i = 0; i < n; i++) {
    cin >> list[i];
    list[i]--;
  }

  vector<int> cnt(n);
  for (int i  = 0; i < n; i++) {
    cnt[list[i]]++;
  }

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    sum += choose2(cnt[i]);
  }

  for (int i = 0; i < n; i++) {
    ll ans = sum;
    ans -= choose2(cnt[list[i]]);
    ans += choose2(cnt[list[i]] - 1);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int n, m, q;
vector<vector<int>> abcd;
int biggest;

void dfs(vector<int> vec){
    if(vec.size() == n){
        int num = 0;
        rep(i, q){
            if(vec[abcd[i][1]-1]-vec[abcd[i][0]-1] == abcd[i][2]){
                num += abcd[i][3];
            }
        }
        biggest = max(biggest, num);
        return;
    }
    for(int i=vec.back(); i<=m; i++){
        vec.push_back(i);
        dfs(vec);
        vec.pop_back();
    }
}

int main() {
    biggest = 0;
    cin >> n >> m >> q;
    rep(i, q){
        vector<int> vec;
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.push_back(a);
        vec.push_back(b);
        vec.push_back(c);
        vec.push_back(d);
        abcd.push_back(vec);
    }
    vector<int> vec;
    for(int i=1; i<=m; i++){
        vec.push_back(i);
        dfs(vec);
        vec.pop_back();
    }
    cout << biggest << endl;
    return 0;
}

Measured memory_bytes: 3636
use std::cmp::min;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n:usize = read();
    let mut mx = read();
    let mut cnt = 1;
    for _ in 1..n {
        let x:usize = read();
        if x <= mx {
            cnt += 1;
        }
        mx = min(mx, x);
    }
    println!("{}", cnt);
}


Measured memory_bytes: 2108
N = int(input())
H = list(map(int, input().split()))

ans = []; count = 0
for i in range(1, N):
    if H[i-1] < H[i]:
        ans.append(count)
        count = 0
    else:
        count += 1
else:
    ans.append(count)

print(max(ans))

Measured memory_bytes: 14252
public class Main {
	public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();

		int result = 0;

		if (A > B) {
			result += A;
			A--;
		} else {
			result += B;
			B--;
		}

		if (A > B) {
			result += A;
			A--;
		} else {
			result += B;
			B--;
		}

		System.out.println(result);
	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++) cin >> a[i];

    vector<int> ans(100005, 0);
    for(int i=0; i<N; i++){
        if(a[i] == 0){
            ans[a[i]]++;
            ans[a[i]+1]++;
        }
        else{
            ans[a[i]]++;
            ans[a[i]+1]++;
            ans[a[i]-1]++;
        }
    }

    int maxv = 0;
    for(int i=0; i<100005; i++) maxv = max(maxv, ans[i]);

    cout << maxv << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll K;
vector<ll> v;

pair<ll,ll> update(ll s, ll e, ll t){
    ll ss = s % t;
    ss = s + ((t-ss)%t);
    ll ee = e % t;
    ee = e - ee;
    //cout << s << " " << e << " " << t << " " << ss << " " << ee << endl;
    if(ss > ee) return {-1,-1};
    if(ss < s || ss > e) return {-1,-1};
    if(ee < s || ee > e) return {-1,-1};
    return {ss,ee};
}

int main(){
    cin >> K;
    for(int i=0;i<K;i++){
        int t;
        cin >> t;
        v.push_back(t);
    }
    reverse(v.begin(),v.end());
    ll s,e;
    s = e = 2;
    for(int i=0;i<K;i++){
        auto p = update(s,e,v[i]);
        if(p.first == -1){
            cout << -1 << endl;
            return 0;
        }
        s = p.first;
        e = p.second + (v[i] - 1);
    }
    cout << s << " " << e << endl;
    return 0;
}

Measured memory_bytes: 1400
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned int  ull;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define int ll
#define pll pair<ll, ll> 
#define pdd pair<ld, ld> 
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 1000000007
using namespace std;

ll power(ll x, ll y){  
	if(x == 1 || y == 0)
		return 1;
    ll res = 1;   
    x = x % mod; 
    if (x == 0) 
		return 0;  
    while (y > 0){  
        if (y & 1)  
	        res = (res * x) % mod;  
        y = y >> 1; 
        x = (x * x) % mod;  
    }  
    return res;  
} 
vi pr;
void sieve(int n){ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++){ 
        if (prime[p] == true){ 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 

    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          pr.pb(p); 
} 
signed main(){
	FASTIO
	int x;
	cin >> x;
	cout << 1 - x;
    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<iostream>
using namespace std;
struct monster{
	int health;
	int strength;
};
int main(){
	monster x,y;
	cin>>x.health>>x.strength;
	cin>>y.health>>y.strength;
	while(x.health>0&&y.health>0){
		y.health-=x.strength;
		if(y.health<=0) break;
		x.health-=y.strength;
	}
	x.health>0?cout<<"Yes":cout<<"No";
	return 0;
} 

Measured memory_bytes: 3620
from collections import deque


def bfs(root):
    global time
    Q = deque()
    distance[root] = 0
    Q.append(root)
    i = root
    while len(Q) > 0:
        i = Q.popleft()
        for v in adjDict[i]:
            if color[v] == 'white':
                Q.append(v)
                color[v] = 'gray'
                distance[v] = distance[i] + 1
        color[i] = 'black'
        label[i] = time


firstline = list(map(int, input().split()))

n = firstline[0]
adjDict = {i: [] for i in range(n)}
color = ['white'] * n
distance = [-1] * n
label = [-1] * n

m = firstline[1]
for _ in range(m):
    adj = list(map(int, input().split()))
    adjDict[adj[0]].append(adj[1])
    adjDict[adj[1]].append(adj[0])

time = 0
for i in range(n):
    if color[i] == 'white':
        bfs(i)
        time += 1

q = int(input())
for _ in range(q):
    question = list(map(int, input().split()))
    if label[question[0]] == label[question[1]]:
        print('yes')
    else:
        print('no')

Measured memory_bytes: 46412
#include<iostream>

using namespace std;

int main (){
  int N,n,tmp;
  cin >> N ;
  tmp =0;
  n =N;
  while(N){
    tmp += N%10;
    N /= 10;
  }
  if( n%tmp == 0){
    cout << "Yes" << endl;
  } else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;



vector<pair<pair<int, int>, int> > edge;
int main(){
  int L;
  cin >> L;
  int N = 0;
  for(int i = 0; i < 30; i++){
    if(L >> i) N = i + 1;
  }
  for(int i = 1; i < N; i++){
    edge.push_back(make_pair(make_pair(i, i+1), 0));
    edge.push_back(make_pair(make_pair(i, i+1), 1 << (N - i - 1)));
  }
  for(int i = 0; i < N - 1; i++){
    if((L >> i)&1){
      edge.push_back(make_pair(make_pair(1, N - i), (L-1) >> (i+1) << (i+1)));
    }
  }

  cout << N << " " << edge.size() << endl;
  for(int i = 0; i < edge.size(); i++){
    cout << edge[i].first.first << " " << edge[i].first.second << " " << edge[i].second << endl;
  }
  
}




Measured memory_bytes: 256
#include<stdio.h>

//料理を表す構造体
struct cuisine {
	int satisfaction;
	int after;
};

int main() {

	//入力
	int n, a[20];
	struct cuisine cuisines[21];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)      scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)     scanf("%d", &cuisines[i].satisfaction);
	for (int i = 1; i <= n - 1; i++) scanf("%d", &cuisines[i].after);
	

	/*順繰りに計算*/

	//合計満足度にまず一品目の満足度を代入
	int ans = cuisines[a[0]].satisfaction;

	for (int i = 1; i < n; i++) {

		//i番目に食べた料理の満足度を追加
		ans += cuisines[a[i]].satisfaction;

		//追加で満足度を得られるのなら、満足度を追加
		if (a[i] - a[i - 1] == 1) {
			ans += cuisines[a[i - 1]].after;
		}
	}

	//出力
	printf("%d\n", ans);

	return 0;
}

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

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") { 
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}
int n, k;

int a[Sz];

ll pref[Sz], p[Sz];

ll dp[Sz][2];
                          
int main()
{
  # ifdef Local
    //localInput();
  # endif
  Read_rap();           
  cin >> n >> k;
  for (int i = 1; i <= n; i++)  cin >> a[i];
  for (int i = 1; i <= n; i++)  pref[i] = pref[i - 1] + a[i], p[i] = p[i - 1] + (a[i] > 0 ? a[i] : 0);
  
  ll ans = 0;
  for (int i = 1; i + k - 1 <= n; i++) {
    ll sum = p[n] - p[i + k - 1] + p[i - 1];
    sum += max (0ll, pref[i + k - 1] - pref[i - 1]);
    ans = max (ans, sum);
  }
  cout << ans;
  return 0;

  for (int i = 1; i <= n; i++) {
    dp[i][0] = max (dp[i - 1][0], dp[i - 1][1]);
    if (i < k) {
      dp[i][1] = -MXLL;
    }
    else {
      static deque <pair <ll, int> > q;
      while (!q.empty() && q.front().y <= i-k)
        q.pop_front();   
      dp[i][1] = max (dp[i - k][0], dp[i - k][1]) + pref[i] - pref[i - k];
      if (!q.empty())
        dp[i][1] = max (dp[i][1], q.front().x + pref[i]);
      ll val = dp[i][1] - pref[i];
      while (!q.empty() && q.back().x > val)
        q.pop_back();
      q.pb ({val, i} );
    }
  }
  cout << max (dp[n][1], dp[n][0]);
                 

  return 0;
}






// Coded by Z..



Measured memory_bytes: 10624
<?php
/*
    Problem URL : http://arc059.contest.atcoder.jp/tasks/arc059_a

    Score  :
    Result :
    Time   : ms
    Memory : KB
 */

fscanf(STDIN, "%d", $N);
$a = explode(" ", trim(fgets(STDIN)));

$aMin = min($a);
$aMax = max($a);
$ans = PHP_INT_MAX;

for ($i = $aMin; $i <= $aMax; $i++) {
    $tmp = 0;
    foreach ($a as $v) {
        $tmp += pow($v - $i, 2);
    }
    $ans = min($ans, $tmp);
}

echo $ans . PHP_EOL;


Measured memory_bytes: 3832
#include<iostream>
#include<stdio.h>
#include<string>
#include<stdlib.h>
using namespace std;
int main() {
	int x1,x2,x3;
	int N;
	cin >> x1>>x2>>x3;
	
	N = x1 * 100 + x2 * 10 + x3;
	if (N % 4 == 0) {
		printf("YES");
	}
	else { cout << "NO"; }
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main() 
{
#ifdef DK
    freopen("in", "r", stdin);
#endif
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(0, c - (a - b)) << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
//#include<math.h>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007ll
#define pb push_back
#define fi firsta
#define se second
#define mk make_pair
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int N, T, ans = INF;
bool flag;

signed main()
{
    cin >> N >> T;
    for(int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        if(b <= T){
            ans = min(ans, a);
            flag = true;
        }
    }
    if(flag)printf("%lld\n", ans);
    else printf("TLE\n");



    return 0;
}
/*


*/



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 500000;
const int MOD = 1000000007;
 
int64_t fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
 
int64_t COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
int main(){
 
  COMinit();
 
  int N,K;
  cin>>N>>K;
  vector<int64_t> A(N);
  for(int i=0;i<N;++i) cin>>A[i];
 
  sort(A.begin(),A.end());
 
  int64_t ans=0;
  for(int i=0;i<N;++i){
    ans += A[i]*(COM(i,K-1)-COM(N-i-1,K-1))%MOD;
  }
  cout<<ans%MOD<<endl;
}

Measured memory_bytes: 12800
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const ll INF64 = 1e18;
const double INFD = 1e30;
const double EPS = 1e-6;
const double PI = 3.14159265;
const ll MOD = 998244353;
template <typename T>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int MAXN = 200005;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE;

bool vis[MAXN];
vector<int> primes;
void sieve(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (vis[i]) continue;
        for (int j = i * i; j <= x; j += i) {
            vis[j] = true;
        }
    }
}
void getprimes(int x) {
    sieve(x);
    for (int i = 2; i <= x; i++) {
        if (!vis[i]) primes.push_back(i);
    }
}

int main() {
#ifdef LOCALLL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    getprimes(200000);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    cout << *lower_bound(primes.begin(), primes.end(), n) << endl;
    return 0;
}

Measured memory_bytes: 640