akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

void W(int line[],int temp[]){
    line[0]=temp[2];
    line[3]=temp[0];
    line[5]=temp[3];
    line[2]=temp[5];
}
void S(int line[],int temp[]){
    line[1]=temp[0];
    line[5]=temp[1];
    line[4]=temp[5];
    line[0]=temp[4];
}
void E(int line[],int temp[]){
    line[2]=temp[0];
    line[5]=temp[2];
    line[3]=temp[5];
    line[0]=temp[3];
}
void N(int line[],int temp[]){
    line[1]=temp[5];
    line[0]=temp[1];
    line[4]=temp[0];
    line[5]=temp[4];
}
int main(void){
    int line[6],i,t,temp[6];
    char ope[101];
    for(i=0;i<6;i++)
        scanf("%d",&line[i]);
    scanf("%s",ope);
    t=0;
    while(ope[t]){
        for(i=0;i<6;i++)
            temp[i]=line[i];
        if(ope[t]=='W')
            W(line,temp);
        else if(ope[t]=='S')
            S(line,temp);
        else if(ope[t]=='E')
            E(line,temp);
        else
            N(line,temp);
        t++;
    }
    printf("%d\n",line[0]);
    return 0;
}

Measured memory_bytes: 596
s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1

        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0 and j > 0:
  if s[i-1]==t[j-1]:
    ans=s[i-1]+ans
    i=i-1
    j=j-1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
print(ans)


Measured memory_bytes: 144532
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x) make_pair(x)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;

//最大公約数をユークリッドの互除法を使って求める

int gcd(int a, int b) {
    if(a % b == 0)
    return b;
    return gcd(b, a % b);
}

 
int main() {

    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n)    cin>>a.at(i);

    int ans=a[0];
    for(int i=1;i<n;i++) {
        ans=gcd(ans,a[i]);
    }
    
    cout<<ans<<endl;

 return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long N;
	cin >> N;
	vector<long long> A(N), B(N);
	for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
	sort(A.begin(), A.end()), sort(B.begin(), B.end());
	long long P = A[(N - 1) / 2] + A[N / 2], Q = B[(N - 1) / 2] + B[N / 2];
	if (N % 2 == 1) cout << Q / 2 - P / 2 + 1 << endl;
	else cout << Q - P + 1 << endl;
}

Measured memory_bytes: 6364
#include <map>
#include <set>
#include <iostream>
#include <vector>
using namespace std;

struct UnionFind{
  vector<int> data;
  UnionFind(int n) : data(n, -1) {}
  bool unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x != y){
      if(data[y] < data[x]) swap(x,y);
      data[x] += data[y];//高さを更新
      data[y] = x;//親を更新
    }
    return x != y;
  }
  bool same(int x, int y){ return find(x) == find(y); }
  int find(int x){
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
};


int main(){
  int n, h, w;
  cin >> n >> w >> h;
  int x, y;
  vector<int> X(n), Y(n);
  map<int,int> M_x, M_y;
  UnionFind uf(n);
  for(int i = 0; i < n; ++i){
    cin >> x >> y;
    X[i] = x;
    Y[i] = y;
    if(M_x[x] > 0){
      uf.unite(i,M_x[x]-1);
    }else{
      M_x[x] = i + 1;
    }
    if(M_y[y] > 0){
      uf.unite(i,M_y[y]-1);
    }else{
      M_y[y] = i + 1;
    }
  }
  set<int> p;
  int l = 0, r = 0, t = 0, b = 0;
  for(int i = 0; i < n; ++i){
    p.insert(uf.find(i));
    if(X[i] == 1 && l == 0) ++l;
    if(X[i] == w && r == 0) ++r;
    if(Y[i] == 1 && b == 0) ++b;
    if(Y[i] == h && t == 0) ++t;
  }
  int k = p.size(), s = l|r|b|t;
  if(k == 1) cout << n - 1 << endl;
  else cout << n + k - 1 - s << endl; 
  return 0;
}



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

// #define int long long // intで書いたけど心配なときにlong longに変換する
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << endl;}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}


signed main() {
    //my-code
    ll x; cin >> x;
    ll a, b;
    a = 1;
    bool loop = true;
    while(loop) {
        REPS(i, -a, a+1) {
            b = i;
            if (a*a*a*a*a-b*b*b*b*b == x) {
                loop = false;
                break;
            }
        }
        if(loop) a++;
    }
    cout << a << " " << b << endl;

    return 0;
}

// https://github.com/kurokoji/.cpp-Template/wiki テンプレートについて
// http://www.creativ.xyz/dump-cpp-652 dump()について
// https://gist.github.com/rigibun/7905920 色々

Measured memory_bytes: 3608
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int D, N, ans = 0; cin >> D >> N;
    int i = 0, j = 1;
    if (D == 0) {
        if (N == 100) ans = 101;
        else {
            while(i < N) {
                if (j % 100 != 0) i++, ans = j, j++;
            }
        }
    }
    else if (D == 1) {
        j = 100;
        while(i < N) {
            if (j % 100 == 0) i++, ans = j, j += 100;
        }
        if (N == 100) ans = 10100;
    }
    else if (D == 2) {
        j = 10000;
        while(i < N) {
            if (j % 10000 == 0) i++, ans = j, j += 10000;
        }
        if (N == 100) ans = 1010000;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3628
import math
from collections import deque

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]
xh.sort(key=lambda x:x[0])
xh = deque(xh)

xh_field = deque()

cnt = 0
now_damage = 0
while xh:
    pos, hp = xh.popleft()
    if xh_field:
        while (xh_field and xh_field[0][0] < pos) :
            now_damage -= a * xh_field[0][1]
            xh_field.popleft() 
    if hp <= now_damage:
        pass
    elif hp > now_damage:
        atk_cnt = math.ceil((hp - now_damage) / a)
        cnt += atk_cnt
        now_damage += atk_cnt * a
        xh_field.append((2*d + pos, atk_cnt))        
print(cnt)


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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

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

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    string S; cin >> S;
    int n = S.size();
    if(n %2 == 1){
        cout << "No" << endl;
        return 0;
    }
    bool ans = true;
    for(int i=0;i<n;i+=2){
        string sub = S.substr(i, 2);
        if(sub != "hi") ans = false;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc012/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using T3 = tuple<int, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 101010;
int dp[MAX][11]; // 頂点 v から 距離 d 以内にある頂点たちの色を塗る.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    int Q;
    vector<T3> q;
    scanf("%d", &Q);
    rep(i, Q){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--;
        q.emplace_back(a, b, c);
    }
    
    // 2. 色を着色する(操作の逆順).
    function<void(int, int, int, int)> f = [&](int pv, int sv, int d, int c) {
        // 距離が負数の場合は, 終了.
        if(d < 0) return;
        
        // 着色済みの場合は, 終了.
        if(dp[sv][d]) return;
        
        // 着色する.
        rep(i, d + 1) if(!dp[sv][i]) dp[sv][i] = c;
        
        // 隣接する頂点を着色.
        for(auto &cv : G[sv]){
            // 親頂点以外を見に行く.
            if(cv != pv) f(sv, cv, d - 1, c);
        }
    };
    repr(i, Q - 1, 0){
        // 操作を取得.
        int v = get<0>(q[i]);
        int d = get<1>(q[i]);
        int c = get<2>(q[i]);
        
        // 頂点の色を塗ってない場合.
        if(!dp[v][d]) f(-1, v, d, c);
    }
    
    // 3. 出力.
    rep(i, N) printf("%d\n", dp[i][0]);
    return 0;
    
}

Measured memory_bytes: 14976
#include<iostream>
using namespace std;
int main(){
int a,b,n,i,j,x[40],y[40],m[17][17];
while(cin>>a>>b,a*a+b*b){
for(i=1;i<=a;i++)
for(j=1;j<=b;j++)m[i][j]=-1;
cin>>n;
for(i=0;i<n;i++){
cin>>x[i]>>y[i];
m[x[i]][y[i]]=0;
}
m[1][1]=1;
for(j=2;j<=b;j++)if(m[1][j]==-1)m[1][j]=m[1][j-1]; 
for(i=2;i<=a;i++){
if(m[i][1]==-1)m[i][1]=m[i-1][1];
for(j=2;j<=b;j++)if(m[i][j]==-1)m[i][j]=m[i-1][j]+m[i][j-1]; 
}
cout<<m[a][b]<<endl;
}
return 0;
}

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

int main()
{
    const int mod = 1e9+7;
    int n, m;
    cin >> n >> m;
    if(n < m) swap(n, m);
    long long ans = 1;
    if(n == m){
        for(int i=1; i<=m; i++) ans = (ans*i)%mod;
        for(int i=1; i<=n; i++) ans = (ans*i)%mod;
        ans = (ans*2)%mod;
    }else if(n == m+1){
        for(int i=1; i<=m; i++) ans = (ans*i)%mod;
        for(int i=1; i<=n; i++) ans = (ans*i)%mod;
    }else{
        ans = 0;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int n, k;
    cin >> n >> k;
    double ans = 0;
    for(int i=1; i<=n; i++){
        int first = i;
        int count = 0;
        if(first < k){
            while(true){
                count++;
                first *= 2;
                if(first >= k) break;
            }
        }
        ans += (1.0/n/pow(2,count));
    }
    cout << fixed << setprecision(10);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
inf = float('inf')
V,E = map(int,input().split())
edge = []
edge_rev = []
for i in range(E):
    A,B,C = map(int,input().split())
    edge_rev.append([B-1,A-1,-C])
    edge.append([A-1,B-1,-C])

d = [inf]*V
d[0] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge[j]
        if d[From] != inf and d[To]>d[From]+cost:
            d[To]=d[From]+cost
            update = True
    if not update:
        break

d_rev = [inf]*V
d_rev[V-1] = 0
for i in range(V):
    update = False
    for j in range(E):
        From,To,cost = edge_rev[j]
        if d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
            d_rev[To]=d_rev[From]+cost
            update = True
    if not update:
        break

d_ = [x for x in d]
d_rev_ = [x for x in d_rev]



for j in range(E):
    From,To,cost = edge[j]
    if d[From] != inf and d_rev[From] != inf and d[To]>d[From]+cost:
        d[To]=d[From]+cost


for j in range(E):
    From,To,cost = edge_rev[j]
    if d[From] != inf and d_rev[From] != inf and d_rev[To]>d_rev[From]+cost:
        d_rev[To]=d_rev[From]+cost


loop = False
for i in range(V):
    if d[i] != 0 and d_rev[i] != 0:
        loop = (d[i]+d_rev[i] != d_[i]+d_rev_[i]) or loop

if loop:
    print('inf')

else:
    ans = -d[-1]
    print(ans)

Measured memory_bytes: 3828
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (input) {
    var num = input.split(' ');
    //??????????????°??????????????????
    var a = parseInt(num[0]);
    var b = parseInt(num[1]);
    var c = parseInt(num[2])
    if ((a < b) && (b < c)) {
        console.log('Yes');
    }
    else {
        console.log('No');
    }
});

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

int main() {
  string s;
  cin>>s;
  if(s=="SRR"){
    cout<<2<<endl;
  }
  else if(s=="RRS"){
    cout<<2<<endl;
  }
  else if(s=="RRR"){
    cout<<3<<endl;
  }
  else if(s=="SSS"){
    cout<<0<<endl;
  }
  else{
    cout<<1<<endl;
  }
}
    
  

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

int main () {
  ll N, K;
  cin >> N >> K;
  
  if (N % K <= abs(K - (N % K))) {
    cout << N % K;
  } else {
    cout << abs(K - (N % K));
  }
}

Measured memory_bytes: 256
//
// Created by わたなべかずき on 2019/12/01.
//

#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
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; }


using namespace std;

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

    // 左から前処理
    vector<long long> S(N*2+1, 0);
    priority_queue<long long, vector<long long>, greater<long long >> que1;
    for(int i = 0; i < N; ++i) {
        S[i+1] = S[i] + a[i];
        que1.push(a[i]);
    }

    for(int i = N; i < N*2; ++i) {
        long long mi = que1.top();
        if (a[i] > mi) {
            S[i+1] = S[i] - mi + a[i];
            que1.pop();
            que1.push(a[i]);
        }
        else  S[i+1] = S[i];
    }

    // 右から前処理
    vector<long long> T(N*2+1, 0);
    priority_queue<long long> que2;
    for(int i = 0; i < N; ++i) {T[i+1] = T[i] + a[N*3-1-i];
        que2.push(a[N*3-1-i]);}


    for(int i = N; i < N*2; ++i) {
        long long ma = que2.top();
        if (a[N*3-1-i] < ma) {
            T[i+1] = T[i] - ma + a[N*3-1-i];
            que2.pop();
            que2.push(a[N*3-1-i]);
        }
        else T[i+1] = T[i];
    }

    long long res = -(1LL<<60);
    for (int i = N; i <= N*2; ++i) {
        res = max(res, S[i] - T[N*3-i]);
    }

    cout << res << endl;
}

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

int main(){
	string s;
	cin >> s;
	int a=0;
	for(int i=0;i<s.size();++i){
		if(s[i]=='A')break;
		else a++;
	}
	for(int i=0;i<s.size();++i){
		if(s[s.size()-i-1]=='Z')break;
		else a++;
	}
	cout << s.size()-a << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		String m;
		int cnt;
		int max;
		
		n = sc.nextInt();
		while (n-- != 0) {
			m = sc.next();
			cnt = 0;
			while (m.length() != 1) {
				max = 0;
				cnt++;
				for (int i = 1; i < m.length(); i++) {
					int le = Integer.parseInt(m.substring(0, i));
					int ri = Integer.parseInt(m.substring(i, m.length()));
					max = Math.max(max, le * ri);
				}
				m = Integer.toString(max);
			}
			
			System.out.println(cnt);
		}
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define IOS                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0);                                                                  \
  cout.tie(0);cout<<fixed<<setprecision(16);
#define ll long long int
#define ld long double
#define el '\n'
#define El '\n'
#define PI (ld)3.141592653589793238462643383279502884197169399375105820974944
#define inf (ll)1000000000
#define mod (ll)1000000007
#define mod1 (ll)998244353
#define fo(i, n) for (long long i = 0; i < n; i++)
#define pll pair<ll, ll>
#define ml map<ll,ll>
#define vpl vector<pll>
#define vvl vector<vector<ll> >
#define vvpl vector< vector<pll> >
#define ff first
#define ss second
#define pqueue priority_queue< ll >
#define pdqueue priority_queue< ll,vl ,greater< ll > >
#define mem(a,b) memset(a,b,sizeof(a));
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sz(a) (ll)a.size()
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define vl vector<ll>
//#define x ff
//#define y ss
#define pt(a) for(auto it:a)cout<<it<<" ";cout<<endl;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;

// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << t<<" "; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << v.first << " " << v.second ; }

double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }

long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1)

      res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}


ll kv;
ll t,n,x,y,h,k,z,p,q,w;
string s,s1,s2;
//vvl v;
//vl vis,d;

int main() {
    IOS;
    cin>>n;
    vl v(n);
    cin>>v;
    fo(i,n)if(v[i]>p)p=v[i],q=i;
    fo(i,n)if(i!=q&&v[i]>x)x=v[i];
    fo(i,n){
        if(i==q)cout<<x<<el;
        else cout<<p<<el;
    }
    return 0;
}


Measured memory_bytes: 3200
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  r,s,p=LI()
  t=S()

  dp=[[0]*3 for _ in range(n+1)]
  for i in range(n):
    a=t[i]
    b=max(dp[i])
    for j in range(3):
      dp[i+1][j]=b
    if i+1<=k:
      if a=='r':
        dp[i+1][2]+=p
      elif a=='s':
        dp[i+1][0]+=r
      else:
        dp[i+1][1]+=s

    else:
      _a,_b,_c=dp[i+1-k]
      if a=='r':
        if not (_c>_a and _c>_b):
          dp[i+1][2]+=p
      elif a=='s':
        if not (_a>_b and _a>_c):
          dp[i+1][0]+=r
      else:
        if not (_b>_a and _b>_c):
          dp[i+1][1]+=s

  # print(dp)
  return max(dp[n])

# main()
print(main())


Measured memory_bytes: 18552
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

int nmemo[100001];
int nlmemo[100001];
int nsmemo[100001];
int lmemo[100001];
int smemo[100001];

void make_memo(const vector<vector<int> > &door, int *memo, const vector<int> &start){
  queue<int> q;
  FOR(it, start){ memo[*it] = 0; q.push(*it); }
  while(q.size()){
    int pos = q.front(); q.pop(); int cnt = memo[pos];
    FOR(it, door[pos]) if(memo[*it] == -1){
      memo[*it] = cnt + 1; q.push(*it);
    }
  }
}

int main(){
  int c; scanf("%d", &c);
  while(c --> 0){
    int n, m;
    scanf("%d%d", &n, &m);
    
    int natsume, lenon;
    scanf("%d%d", &natsume, &lenon);

    vector<vector<int> > ndoor(n+1);
    vector<vector<int> > ldoor(n+1);

    REP(i, m){
      int a, b; char p;
      scanf("%d%d %c", &a, &b, &p);
      if(p == 'N'){
	ndoor[a].push_back(b);
	ndoor[b].push_back(a);
      }else{
	ldoor[a].push_back(b);
	ldoor[b].push_back(a);
      }
    }

    REP(i, n+1) nsmemo[i] = nlmemo[i] = nmemo[i] = lmemo[i] = smemo[i] = -1;

    make_memo(ndoor, nmemo, vector<int>(1, natsume));
    make_memo(ldoor, lmemo, vector<int>(1, lenon));
    make_memo(ldoor, smemo, vector<int>(1, 0));

    if(lmemo[0] != -1){
      print(0);
    }else{
      vector<int> l; REP(i, n+1) if(lmemo[i] != -1) l.push_back(i);
      vector<int> s; REP(i, n+1) if(smemo[i] != -1) s.push_back(i);
      make_memo(ndoor, nlmemo, l);
      make_memo(ndoor, nsmemo, s);
      
      int ans = INT_MAX;
      REP(i, n+1) if(nmemo[i] != -1 && nsmemo[i] != -1 && nlmemo[i] != -1)
	ans = min(ans, nmemo[i] + nsmemo[i] + nlmemo[i]);
      
      print(ans);
    }
  }
  
  return 0;
}

Measured memory_bytes: 7052
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;
//const int mod = 998244353;
const int INF = 1001001001;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};

struct mint {
  ll x;
  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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main()
{
    string s;
    cin >> s;
    int mn = INF, mx = 0;
    rep(i, 0, s.size()){
        if(s[i] == 'A') mn = min(mn, i);
        if(s[i] == 'Z') mx = max(mx, i);
    }
    cout << mx - mn + 1 << endl;
    return 0;
}


Measured memory_bytes: 3716
/*  AC祈願アンコウ
   　／￣＼
   ○    ／￣￣￣＼ヘ
    　 /・　 ・　 ＼>   
    ／￣￣￣＼　　  Ｖ| 
    ｜ ――― ｜　　  ｜|
    ＼＿＿＿／　　  ∧|
    　　＼　　　　／
    　　　￣￣￣￣
*/

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

typedef int64_t ll;
//static const int MOD = 1000000007;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const int INF = 1000010000;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define NP next_permutation
#define PQ priority_queue
#define UB upper_bound
#define LB lower_bound
#define SZ(a) int((a).size())
#define LEN(a) int((a).length())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REP1(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREP1(i,x) for(int i=((int)(x));i>0;i--)
#define ALL(x) (x).begin(),(x).end()
#define YESNO(x) puts((x)?"YES":"NO")
#define YesNo(x) puts((x)?"Yes":"No")


signed main(){
    int a,b,c;
    cin >> a >> b >> c;
    YesNo(a+b>=c);

    return 0;
}


Measured memory_bytes: 256
/* winners never quit and quitters never win.
      #swap                                 */
      
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize ("-O3")
using ll = long long;
using ld = long double;
const ll mod = 1000000007;
const ll inf = 1000000000000000000;
const ll rk = 256;
const ld PI = 3.141592653589793;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

template <typename T>
void make_unique(vector<T>& vec) {
  sort(all(vec));
  vec.erase(unique(all(vec)), vec.end());
}

#define endl '\n'
#define pb push_back
#define mp make_pair
#define vc vector
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll> 
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define all(x) (x).begin(), (x).end()
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

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

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define T ll t=0;cin>>t;for(ll test=0;test<t;test++)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


ll nxt() {
    ll TemporaryVariable;
    cin >> TemporaryVariable;
    return TemporaryVariable;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
	//isprime();
	//coeff();
	/*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    /*rlimit rlim;
    if (getrlimit(RLIMIT_STACK, &rlim)) return 1;
    rlim.rlim_cur = rlim.rlim_max;
    if (setrlimit(RLIMIT_STACK, &rlim)) return 2;*/
    ll n=nxt();
    string s;
    cin>>s;
    ll ans=0,cnt=0;
    rep(a,0,n)
        cnt+=(s[a]=='R');
    rep(a,0,cnt)
        ans+=(s[a]=='W');
    cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 3796
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    if(a-b > 0){
        cout << a-b;
    }
    else
    {
        cout << 0;
    }
    
    cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll,ll> lp;
const int inf=0x3f3f3f3f;
void A() {
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0; i<n; i++)
        cin>>a[i];
    vector<int> dp(n+1,inf);
    dp[0]=0;
    for(int i=1; i<n; i++) {
        dp[i]=min(dp[i],dp[i-1]+abs(a[i]-a[i-1]));
        if(i>=2)
            dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1]<<endl;

}
void B() {
    int n,k;
    cin>>n>>k;
    vector<int> dp(n+1,inf);
    vector<int> h(n,0);
    for(int i=0; i<n; i++)
        cin>>h[i];
    dp[0]=0;
    for(int i=1; i<n; i++) {
        for(int len=1; len<=min(k+1,i+1); len++) {
            int j=i-len+1;
            dp[i]=min(dp[i],dp[j]+abs(h[j]-h[i]));
        }
    }
    cout<<dp[n-1]<<endl;
}
void C() {
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(3,0));
    for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];
    vector<vector<int>> dp(n,vector<int>(3,0));
    dp[0][0]=a[0][0];
    dp[0][1]=a[0][1];
    dp[0][2]=a[0][2];
    for(int i=1; i<n; i++) {
        for(int j=0; j<3; j++) {
            for(int k=0; k<3; k++) {
                if(j==k)
                    continue;
                dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
                //cout<<dp[i][j]<<endl;
            }
        }
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
}
void D()
{
    ll n,W;
    cin>>n>>W;
    vector<lp> p;
    for(int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        p.emplace_back(a,b);
    }
    sort(p.begin(),p.end());
    vector<ll> dp(W+1,0);
    for(int i=0;i<n;i++){
        for(int j=W;j>=p[i].first;j--){
            if(j>0) dp[j]=max(dp[j],dp[j-1]);
            dp[j]=max(dp[j],dp[j-p[i].fi]+p[i].se);
        }
    }
    cout<<dp[W]<<endl;

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


Measured memory_bytes: 3980
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli mod=1000000007;

int main()
{
	ios_base::sync_with_stdio(false); 
	string s;
	cin>>s;
	lli q;
	cin>>q;
	lli rev=0;
	vector<char> front;
	vector<char> back;
	for(lli i=0;i<q;++i){
		lli type;
		cin>>type;
		if(type==1){
			rev=1-rev;
		}
		else{
			lli type;
			char c;
			cin>>type;
			cin>>c;
			if(rev){
				if(type==1)
					type=2;
				else
					type=1;
			}
			if(type==1)
				front.push_back(c);
			else
				back.push_back(c);
		}
	}	
	if(rev){
		if(back.size())
		for(lli i=back.size()-1;i>=0;--i)
			cout<<back[i];
		reverse(s.begin(),s.end());
		cout<<s;
		if(front.size())
		for(lli i=0;i<front.size();++i)
			cout<<front[i];
	}
	else{
		if(front.size())
			for(lli i=front.size()-1;i>=0;--i)
				cout<<front[i];
		cout<<s;
		for(lli i=0;i<back.size();++i)
			cout<<back[i];
	}
}

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair



char solve(string& s, ll k) {
    --k;
    int L = s.size();
    ll base = 0;
    for (int i=0; i<L; ++i) {
        if (s[i] == '1') {
            if (base == k) return '1';
            base += 1;
        } else {
            // base += x ^ 5000兆
            return s[i];
        }
    }
    return '?';
}

int main() {
    string s; cin >> s;
    ll k; cin >> k;
    cout << solve(s,k) << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
B = list(map(int,input().split()))
sum = 0
if N == 2:print(B[0]*2)
else:
    sum += B[0]
    for i in range(0,N-2):
        sum += min(B[i],B[i+1])
    sum += B[N-2]
    print(sum)

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

ll mod = 1000000007;


int main() {
int n; cin >> n;
vector<int> s(n);
rep(i,n) cin >> s[i];
int total=0;
rep(i,n) total+=s[i];
vector<int> t(n);
rep(i,n){
    t[i]=s[i];
    if (t[i]%10==0) t[i]=101;  
}
sort(t.begin(),t.end());
if(total%10!=0){cout << total <<endl;
return 0;}
if(total%10==0&&t[0]==101) cout << 0 <<endl;
else cout <<total-t[0]<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
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 power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}

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

    string inp;
    cin >> inp;
    sort(all(inp));
    
    if(inp[0] == inp[1] and
       inp[2] == inp[3] and
       inp[1] != inp[2]) cout << "Yes" << endl;
    else cout << "No" << endl;

    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


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

int main() {
 int64_t a, b, k;
   cin >> a >> b >> k;
 if(k<=a) cout << a-k << " " << b << endl;
  else if(k<=b+a) cout << 0 << " " << a+b-k<< endl;
  else cout << 0 << " " << 0 << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp11
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            string S = Console.ReadLine();

            char[] A = new char[S.Length];
            int num;
            string ans = "";
            for(int i = 0; i < S.Count(); i++)
            {
                num = S[i] + N;
                if (num > 90)
                {
                    num -= 26;
                }
                A[i] = (char)num;
                ans += A[i];
            }

            Console.WriteLine(ans);
        }
    }
}

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

#define all(x) (x).begin(),(x).end()
#define isz(x) (int)(x).size()

template<class C, class X>
int lowpos(const C& c, X x) {
    return int(std::lower_bound(all(c), x) - c.begin());
}

template<class C, class X>
int uppos(const C& c, X x) {
    return int(std::upper_bound(all(c), x) - c.begin());
}

using pii = std::pair<int,int>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;

struct Edge { int u, v; };

const int MAX = (int)1e9;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n, m; std::cin >> n >> m;
    std::vector<pii> arr(n);
    for (auto &it : arr) {
        std::cin >> it.first >> it.second;
    }
    arr.push_back(pii{0,0});
    arr.push_back(pii{MAX+1,0});
    std::sort(all(arr));
    // transform to xor:
    vi d;
    for (int i = 1; i < isz(arr); i++) {
        d.push_back(arr[i].second ^ arr[i-1].second);
    }
    
    // building graph:
    std::vector<Edge> edges(m);
    vvi adj(isz(d));
    for (int i = 0; i < m; i++) {
        int l, r; std::cin >> l >> r;
        int u = lowpos(arr, pii(l, 0))-1;
        int v = uppos(arr, pii(r,1))-1;
        assert(0 <= u && u <= v && v < isz(d));
        edges[i] = Edge{u,v};
        if (u < v) {
            adj[u].push_back(i);
            adj[v].push_back(i);
        }
    }
    // dfs over connected components:
    vi take(m), color(isz(d));
    std::function<void(int,int,int)> dfs = [&](int u, int p, int id) {
        if (color[u] != 0) return;
        color[u] = 1;
        for (int eid : adj[u]) {
            const auto & e = edges[eid];
            int v = e.u + e.v - u;
            if (v == p) continue;
            if (color[v] == 0) {
                dfs(v,u,eid);
            }
        }
        if (d[u] == 1 && p >= 0) {
            take[id] = 1;
            d[u] ^= 1;
            d[p] ^= 1;
        }
        color[u] = 2;
    };
    bool answ = true;
    for (int u = 0; u < isz(d); u++) {
        if (color[u] == 0) {
            dfs(u,-1,-1);
        }
        answ = answ && (d[u] == 0);
    }
    // writing answer:
    if (!answ) {
         std::cout << "-1" << std::endl;
    } else {
        vi k;
        for (int i = 0; i < m; i++) {
            if (take[i]) {
                k.push_back(i+1);
            }
        }
        std::cout << isz(k) << "\n";
        for (int it : k) std::cout << it << ' ';
        std::cout << std::endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;

const int maxn = 200;
const int maxw = 1e5+10;
const int INF = 1e9+10;

ll dp[maxn][maxw];
int v[maxn];
int n,w;
int wt[maxn];

ll knapsack(int i,int wgt){
	if(wgt < 0)
		return -INF;
	if(i == n) 
		return 0;
	ll& pdm = dp[i][wgt];
	if(pdm != -1) return pdm;
	return pdm = max(knapsack(i+1,wgt),
		knapsack(i+1,wgt-wt[i])+v[i]);
}

void solve(){
	cin >> n >> w;
	for(int i=0;i<n;++i){
		cin >> wt[i];
		cin >> v[i];
	}
	memset(dp,-1,sizeof dp);
	cout << knapsack(0,w) << '\n';
}

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

Measured memory_bytes: 156544
#include <bits/stdc++.h>
#define pb push_back
#define sz(a) int(a.size())
#define re return
#define all(a) a.begin(),a.end()
using namespace std;
int main()
{
	string s;
	cin>>s;
	string ans="Yes";
	if (sz(s)%2)  ans="No";
	for (int i=0;i<sz(s);i++){
		if (i%2==0 && s[i]!='h')  ans="No";
		if (i%2 && s[i]!='i')  ans="No";
	}
	cout<<ans;
	re 0;
}

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

int main() {
    string s; cin >> s;
    int n = s.size();
    vector<int> ans(n);
    rep(ri,2) {
        {
            int cnt = 0;
            rep(i,n) {
                if(s[i] == 'R') cnt++;
                else {
                    ans[i] += cnt/2;
                    ans[i-1] += (cnt+1)/2;
                    cnt = 0;    
                }
            }
        }
        reverse(ans.begin(),ans.end());
        reverse(s.begin(),s.end());
        rep(i,n) {
            if(s[i] == 'L') s[i] = 'R';
            else s[i] = 'L';
        }
    }
    rep(i,n){
        if(i == 0) cout << ans[i];
        if(i) cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

vector<int> P;

int main () {
    int h, w, n;
    cin >> h >> w >> n;

    int big = max(h, w);


    cout << ceil(1.0 * n / big) << endl;
}

Measured memory_bytes: 256
/* Code by Saborit */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast") 
#define MX 100005
#define INF (1<<30)
#define EPS 1e-9
#define MOD 1000000007
#define mid (x+xend)/2
#define izq nod*2
#define der nod*2+1
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
#define unique(X) (X).resize(unique(all(X)) - (X).begin())
#define d(X) cerr << #X << " = " << X << endl;
using namespace std;
using namespace __gnu_pbds;
typedef long long int64;
typedef unsigned long long unt64;

int N;
int dp[MX], A[MX];

int main(void){
    //~ freopen("a.in", "r", stdin);
    //~ freopen("a.out", "w", stdout);
    
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
		scanf("%d", &A[i]);	
	} 
	
	dp[1] = 0;
	dp[2] = abs(A[2] - A[1]);
	
	for(int i=3; i<=N; i++){
		dp[i] = min(dp[i-1] + abs(A[i-1]- A[i]), dp[i-2] + abs(A[i-2]- A[i]));
	}
	
    printf("%d\n", dp[N]);    

   return 0;
}


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

vector<pair<long long,long long> >prime_factorize(long long N){
    vector<pair<long long, long long>> res;
    for(long long a=2;a*a<=N;a++){
        if(N%a!=0) continue;
        long long ex=0;
        while(N%a==0){
            ex++;
            N /= a;
        }
        res.push_back({a,ex});
    }
    if(N!=1) res.push_back({N,1});
    return res;
}

int main(){
   long long N;
   cin >> N;

   const int mod=1000000007;
   vector<long long> ex(N+1,0);
   for(long long n=2;n<=N;n++){
       const auto &res = prime_factorize(n);
       for(auto p:res) ex[p.first] +=p.second;
   }
   long long res=1;
   for(int p=2;p<=N;p++){
       res *= ex[p]+1;
       res %= mod;
   }
   cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
using namespace std;
#define mod 1000000007
const int maxn=1000000;
int dp[3005][3005];
//int lcs(string a,string b,int n,int m) {
//    if (n == 0 or m == 0) return 0;
//    if (dp[n][m] != -1) return dp[n][m];
//    if (a[n - 1] == b[m - 1]) {
//        return dp[n][m] = 1 + lcs(a, b, n - 1, m - 1);
//    }
//    int x = lcs(a, b, n - 1, m);
//    int y = lcs(a, b, n, m - 1);
//    return dp[n][m] = max(x, y);
//}
void solve() {
    string a, b;
    cin >> a >> b;
    int n=a.size(),m=b.size();
    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][j-1],dp[i-1][j]);
            }
        }
    }
    int i=n,j=m;
    string ans;

    while (i > 0 and j > 0) {
        if (a[i - 1] == b[j - 1]) {
            ans += a[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else j--;
    }
    reverse(all(ans));
    cout<<ans;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

Measured memory_bytes: 74008
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var stdInScanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
	stdInScanner.Scan()
	i, _ := strconv.Atoi(stdInScanner.Text())
	return i
}

func main() {
	stdInScanner.Split(bufio.ScanWords)

	A := nextInt()
	B := nextInt()
	C := nextInt()
	D := nextInt()

	for {
		C -= B
		if C <= 0 {
			fmt.Println("Yes")
			break
		}
		A -= D
		if A <= 0 {
			fmt.Println("No")
			break
		}
	}
}


Measured memory_bytes: 1756
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	short to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///


int d[5005];
vector<vector<edge>> es;

void dijkstra(int s)
{
	fill(ALL(d), INF);
	d[s] = 0;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		REP(i, es[v].size())
		{
			edge e = es[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	int n, k;
	bool memo[5000];
	cin >> n >> k;
	es.clear();
	es.resize(n);
	short c[5000], r[5000];
	REP(i, n) cin >> c[i] >> r[i];
	vector<vi> v(n);
	REP(i, k)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	vector<short> res;
	queue<P> que;
	REP(i, n)
	{
		MS(memo, 0);
		res.clear();
		while (que.size()) que.pop();
		que.push(P(i, 0));
		while (que.size())
		{
			int tmp = que.front().first;
			int dis = que.front().second;
			memo[tmp] = true;
			que.pop();
			if (dis > r[i]) break;
			res.push_back(tmp);
			REP(j, v[tmp].size())
			{
				if (!memo[v[tmp][j]])
				{
					que.push(P(v[tmp][j], dis + 1));
				}
			}
		}
		REP(j, res.size()) es[i].push_back(edge{ res[j], c[i] });
	}
	dijkstra(0);
	cout << d[n - 1] << endl;
	return 0;
}

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

using namespace std;

using ll = long long;

int main(){
    int  N, M;
    cin >> N >> M;

    int a[M];

    vector<int> oks(N+1, true);
    for (int i = 0; i < M; i++){
        cin >> a[i];
        oks[a[i]] = false;
    }

    vector<long long> dp(N+1);
    dp[0] = 1;

    for (int now = 0; now < N; now++){
        for (int next = now+1; next <= min(now+2, N); next++){
            if(oks[next]){
                dp[next] += dp[now];
                dp[next] %= 1000000007;
            }
        }
    }

    cout << dp[N] << endl;
}



    


Measured memory_bytes: 1792