akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int main(){
    int N;
    cin >> N;
    int BA = 0, XA = 0, BX = 0;
    int ans = 0;
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        for(int j = 0; j + 1 < s.size(); j++){
            if(s[j] == 'A' && s[j + 1] == 'B')ans++;
        }
        if(s[0] == 'B' && s[s.size() - 1] == 'A')BA++;
        else if(s[0] == 'B')BX++;
        else if(s[s.size() - 1] == 'A')XA++;
    }
    if(XA && BX){
        ans += min(XA, BX) + BA;
    }
    else if(XA){
        ans += BA;

    }
    else if(BX){
        ans += BA;
    }
    else if(BA){
        ans += (BA - 1);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
slectionSort(int a[],int n){ 
    int i,j,tmp,count=0,minj;
    for(i=0;i<n-1;i++){
        minj=i;
        for(j=i;j<n;j++){   
            if(a[j] < a[minj]){
                minj=j;
            }
        }
        tmp=a[i];
        a[i]=a[minj];
        a[minj]=tmp;
        if(i!=minj){
            count++;    
        }
    } 
    return count;
}
int main(void){
    int a[100],n,i,count;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    count=slectionSort(a,n);
    for(i=0;i<n;i++){
        if(i>0){
            printf(" ");
        }
        printf("%d",a[i]);
        
    }
    printf("\n");
    printf("%d\n",count);
    return 0;
}


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

int main(){
  int N; cin >> N;
  vector<int> d(N);
  for(int i = 0; i < N; i++){
    cin >> d[i];
  }
  int sum = 0;
  for(int i = 0; i < N; i++){
    for(int j = i+1; j < N; j++){
      sum += d[i] * d[j];
    }
  }
  cout << sum;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    s = input().rstrip()

    n = len(s)

    if s == s[::-1]:
        if s[:int((n-1)/2)] == s[:int((n-1)/2)][::-1]:
            if s[int((n+1)/2):] == s[int((n+1)/2):][::-1]:
                print('Yes')
            else:
                print('No')
        else:
            print('No')
    else:
        print('No')

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
let readIntArray _ =
    stdin.ReadLine().Split(" ") |> Array.map int

readIntArray ()
|> fun [| a; b |] ->
    let zip = stdin.ReadLine().Split("-")
    match zip with
    | [| x; y |] -> if x.Length = a && y.Length = b then "Yes" else "No"
    | _ -> "No"
|> printfn "%s"


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


int main()
{
    int n;
    cin >> n;
    vector<int> ans(n+1, 0);

    for(int x = 1; x*x < n; x++)
    {
        for(int y=1; y*y < n; y++)
        {
            for(int z = 1; z*z < n; z++)
            {
                int p = x*x + y*y + z*z + x*y + y*z + z*x;
                if(p > n) continue;
                ans[p]++;
            }
        }
    }

    for(int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
        
    return 0;
}

Measured memory_bytes: 3540
h = int(input())
mem = [0] * 100
cnt = 0
 
def atk(k):
    if k == 1:
        mem[1] = 1
        return 1
    else:
        j = int(k // 2)
        l = 0
        while k / ( 2 ** l) >1:
            l += 1
 
        if mem[l] == 0:
            mem[l] = atk(j) * 2 + 1
            return mem[l]
        else:        
            return mem[l]

atk(h)
mem.sort(reverse = True)
print(mem[0])

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

int main() {
    long long int n, i, j, k, ans=0, march[5]={0,0,0,0,0};
    string s;
    cin >> n;
    while(cin >> s) {
        if(s[0] == 'M') march[0]++;
        if(s[0] == 'A') march[1]++;
        if(s[0] == 'R') march[2]++;
        if(s[0] == 'C') march[3]++;
        if(s[0] == 'H') march[4]++;
    }
    
    for(i=0; i<5; i++)
        for(j=i+1; j<5; j++)
            for(k=j+1; k<5; k++)
                    ans += march[i] * march[j] * march[k];
    
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll MOD = 1000000007;
const ll N=1e5+9;
int main()
{
    FASTINOUT;
    ll x,a,b;
    cin>>x>>a>>b;
    if (a==0)
        cout<<0<<endl;
    else{
    ll ans=x/(a+b)*a+min(x%(a+b),a);
    cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define rrep(i,m,n) for(int i = m; i >= n; i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
bool comp(lpair l1, lpair l2){
    return (l1.second > l2.second);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,W;
    ll w[110], v[110];
    cin >> N >> W;
    rep(i,0,N){
        cin >> w[i] >> v[i];
    }
    ll w0 = w[0];
    vector<lpair> p1, p2, p3, p4;
    rep(i,0,N){
        if(w[i] == w0){
            p1.push_back(make_pair(w[i], v[i]));
        }else if(w[i] == w0+1){
            p2.push_back(make_pair(w[i], v[i]));
        }else if(w[i] == w0+2){
            p3.push_back(make_pair(w[i], v[i]));
        }else{
            p4.push_back(make_pair(w[i], v[i]));
        }
    }
    sort(p1.begin(), p1.end(), comp);
    sort(p2.begin(), p2.end(), comp);
    sort(p3.begin(), p3.end(), comp);
    sort(p4.begin(), p4.end(), comp);
    ll sum1[110] = {}, sum2[110] = {}, sum3[110] = {}, sum4[110] = {};
    ll n1 = p1.size();
    ll n2 = p2.size();
    ll n3 = p3.size();
    ll n4 = p4.size();
    rep(i,0,n1){
        sum1[i+1] = sum1[i] + p1[i].second;
    }
    rep(i,0,n2){
        sum2[i+1] = sum2[i] + p2[i].second;
    }
    rep(i,0,n3){
        sum3[i+1] = sum3[i] + p3[i].second;
    }
    rep(i,0,n4){
        sum4[i+1] = sum4[i] + p4[i].second;
    }
    ll ans = 0;
    rep(i,0,n1+1){
        rep(j,0,n2+1){
            rep(k,0,n3+1){
                rep(m,0,n4+1){
                    ll weigh = i * w0 + j * (w0+1) + k * (w0+2) + m * (w0+3);
                    ll val = sum1[i] + sum2[j] + sum3[k] + sum4[m];
                    if(weigh <= W){
                        ans = max(ans, val);
                    }
                }
            }
        }

    }
    print(ans);

}


Measured memory_bytes: 256
n, k = map(int,input().split())
dat = list(map(int, input().split()))
i = dat.index(1) + 1 # 1originでi個目に1がある
import math

b1 = k # 今1で占有した場所
a1 = 1 # 1にたどり着くまでに必要な個数
a2 = 0
if b1 < i: # もし、iがいまよりも手前にあるなら
    a2 += math.ceil( (i - k) / (k - 1) )
b1 += a2 * (k - 1)
b1 = n if b1 > n else b1 # 1のターンでたどり着いた場所
a3 = math.ceil((n - b1) / (k - 1))
print(a1+a2+a3)

Measured memory_bytes: 52476
from collections import Counter
N, M = map(int, input().split())
As = list(map(int, input().split()))

ct = Counter()
ct[0] = 1
s = 0
ans = 0
for a in As:
    s += a
    mod = s % M
    ans += ct[mod]
    ct[mod] += 1
print(ans)

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
  int n;
  cin >> n;
  int l = 0, r = n - 1;
  cout << 0 << endl;
  string s;
  cin >> s;
  if(s == "Vacant") return 0;
  for(int i = 0; i < 20; i++) {
    if(l > r) {
      cout << n - 1 << endl;
      return 0;
    }
    int mid = (l + r) / 2;
    cout << mid << endl;;
    string ans;
    cin >> ans;
    if(ans == "Vacant") return 0;
    else {
      if(mid % 2 == 0) {
        if(ans == s) l = mid + 1;
        else r = mid - 1;
      }else {
        if(ans == s) r = mid - 1;
        else l = mid + 1;
      }
    }
  }
}


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

void print( const vector<int>& a ) {
	int n = a.size();

	for( int i = 0; i < n; ++i ) {
		cout << a.at( i );

		if( i < n-1 ) { cout << ' '; }
	}

	cout << endl;
}

int bubbleSort( vector<int>& A, int N ) {
	int count = 0;
	bool flag = true;

	while( flag ) {
		flag = false;

		for( int j = N-1; j > 0; --j ) {
			if( A.at( j ) < A.at( j-1 ) ) {
				swap( A.at( j ), A.at( j-1 ) );
				count += 1;
				flag = true;
			}
		}
	}

	return count;
}

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

	vector<int> a( N );
	for( auto& v: a ) { cin >> v; }

	int count = bubbleSort( a, N );
	print( a );

	cout << count << endl;
}



Measured memory_bytes: 3096
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define LL long long
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(), (v).end()
#define FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())

LL A, B, Q;
LL s[100010], t[100010];

int rightS[100010];
int rightT[100010];

void init() {

}

void input() {
  cin >> A >> B >> Q;
  REP(i, A) cin >> s[i];
  REP(i, B) cin >> t[i];
  sort(s, s+A);
  sort(t, t+B);
}

LL dstNearS(LL x) {
  LL res = 1LL<<55;
  int p = lower_bound(s, s+A, x) - s;
  if (p < A) {
    chmin(res, s[p]-x);
  }
  if (p > 0) {
    chmin(res, x-s[p-1]);
  }
  return res;
}

LL dstNearT(LL x) {
  LL res = 1LL<<55;
  int p = lower_bound(t, t+B, x) - t;
  if (p < B) {
    chmin(res, t[p]-x);
  }
  if (p > 0) {
    chmin(res, x-t[p-1]);
  }
  return res;
}

LL calc(LL x) {
  LL res = 1LL<<55;

  int p = lower_bound(s, s+A, x) - s;
  if (p < A) {
    chmin(res, s[p]-x + dstNearT(s[p]));
  }
  if (p > 0) {
    chmin(res, x-s[p-1] + dstNearT(s[p-1]));
  }

  p = lower_bound(t, t+B, x) - t;
  if (p < B) {
    chmin(res, t[p]-x + dstNearS(t[p]));
  }
  if (p > 0) {
    chmin(res, x-t[p-1] + dstNearS(t[p-1]));
  }

  return res;
}

void solve() {
  REP(i, A) {
    rightS[i] = lower_bound(t, t+B, s[i]) - t;
  }
  REP(i, B) {
    rightT[i] = lower_bound(s, s+A, t[i]) - s;
  }
  REP(_, Q) {
    LL x;
    cin >> x;
    cout << calc(x) << endl;
  }
}

int main() {
	init();
	input();
	solve();
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second 
using namespace std;
typedef long long ll;
const ll INF = 1e18+5;
int main(){
	fastio;
	string str1,str2;
	cin>>str1>>str2;
	ll n1 = str1.size();
	ll n2 = str2.size();
	vector< vector< pair<ll,pair<ll,ll> > > > dp(n1+1,vector< pair<ll,pair<ll,ll> > > (n2+1, {0, {0,0}}));

	for(ll i=1;i<=n1;i++){
		for(ll j=1;j<=n2;j++){
			
			if(str1[i-1]==str2[j-1]){
				dp[i][j] = make_pair(1+dp[i-1][j-1].fi,make_pair(i-1,j-1));
			}
			else {
        if(dp[i-1][j]>dp[i][j-1]){
          dp[i][j] = make_pair(dp[i-1][j].fi,make_pair(i-1,j));
        }
        else{
          dp[i][j] = make_pair(dp[i][j-1].fi,make_pair(i,j-1));
        }

				
			}
		}
	}

  pair<ll,pair<ll,ll> > ans = dp[n1][n2];
  pair<ll,ll> cur = ans.se;
  string res = "";

  if(str1[n1-1]==str2[n2-1]){
    res += str1[n1-1];
  }

  while((cur.fi>0)&&(cur.se>0)){
    ll i=cur.fi;
    ll j=cur.se;
    //cout<<"("<<i<<j<<")"<<"\n";
    if(str1[i-1]==str2[j-1]){
      res += str1[i-1];
    }
    cur = make_pair(dp[i][j].se.fi,dp[i][j].se.se);


  }

  reverse(res.begin(),res.end());
  cout<<res<<"\n";

	
}

Measured memory_bytes: 211584
#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    if(a[0] == 5 && a[1] == 5 && a[2] == 7) {
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

Measured memory_bytes: 256
input_lines = input()
N_A_B = input_lines.split()
N = int(N_A_B[0])
A = int(N_A_B[1])
B = int(N_A_B[2])
while 1 <= A < B <= N:
    if A + 1 < B:
        A = A + 1
    elif 1 < A and A + 1 == B:
        A = A - 1
    elif 1 == A and A + 1 == B:
        print("Borys")
        break
    if A < B - 1:
        B = B - 1
    elif A == B - 1 and B < N:
        B = B + 1
    elif A == B - 1 and B == N:
        print("Alice")
        break
else:
    print("draw")


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

ll N, K;
vll A;

ll count(ll l){
  ll ans = 0;
  REP(i,N){
    ans += (A[i]-1)/l;
  }
  return ans;
}

ll binary_search(ll begin, ll end){
  if(end-begin<=1){
    if(count(begin)<=K){
      return begin;
    }
    return end;
  }
  ll mid = (begin+end)/2;
  if(count(mid)<=K){
    return binary_search(begin, mid);
  }
  return binary_search(mid, end);
}

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  IN(N,K);
  A.resize(N);
  REP(i,N){
    IN(A[i]);
  }

  ll ans = binary_search(1, 1E9+7);

  OUT(ans);

  return 0;
}


Measured memory_bytes: 4688
#include <stdio.h>

int abvalue(int m, int n);

int main(void)
{
    int A1;
    int A2;
    int A3;
    int c = scanf("%d %d %d", &A1, &A2, &A3);
    int r;

    if (A1 <= A2 && A2 <= A3 || A3 <= A2 && A2 <= A1)
    {
        r = abvalue(A1, A3);
    }
    else if (A1 <= A3 && A3 <= A2 || A2 <= A3 && A3 <= A1)
    {
        r = abvalue(A1, A2);
    }
    else if (A2 <= A1 && A1 <= A3 || A3 <= A1 && A1 <= A2)
    {
        r = abvalue(A2, A3);
    }

    printf("%d\n", r);
    return 0;
}

int abvalue(int m, int n)
{
    int result;
    if (m < n)
    {
        result = n - m;
    }
    else
    {
        result = m - n;
    }

    return result;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
int main(){
ll blah[90];
string s;
cin >> s ;
ll len= s.size();

 blah['N']=0,blah['S']=0,blah['E']=0,blah['W']=0;
for( ll i = 0 ; i<len ; i++){

    if(s[i]== 'N') blah['N']=1;
    else if(s[i]=='S') blah['S']=1;
    else if (s[i]=='E') blah['E']=1;
    else blah['W'] = 1;

}
if(blah['N']!=blah['S']) cout<<"No"<<endl;

else if(blah['E']!=blah['W']) cout<<"No"<<endl;

else cout<<"Yes"<<endl;
return 0;
}






Measured memory_bytes: 256
#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 (1e18)

int main(){
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    int f[n] = {};
    rep(i, n){
        rep(j, 5)rep(k, 2) {
            int tmp;
            cin >> tmp;
            f[i] = f[i] * 2 + tmp;
        }
    }
    int p[n][11];
    rep(i, n)rep(j, 11) cin >> p[i][j];
    ll maxi = -INF;
    repl(i, 1, 1 << 10) {
        ll tmp = 0;
        rep(j, n) tmp += p[j][bcnt((i & f[j]))];
        maxch(maxi, tmp);
    }
    cout << maxi << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;

const int N = 1e5 + 5;
const long long INF = 1e18;
const int mod = 1000000007;//786433;//998244353;
const double Pi = acos(-1);

 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int n;
long long a, res = 1;

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a;
		if(a == 0)
		{
			cout << 0;
			return 0;
		}
		if(res > INF / a)
		{
			res = -1;
		}
		if(res != -1)
		{
			res *= a;
		}
	}
	cout << res;
}

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

int n, k, st[300005<<2], ans;

void update(int x, int l, int r, int u, int d){
    st[x] = max(st[x], d);
    if (l == r) return;
    int mid = (l+r)/2;
    if (u <= mid) update(x<<1, l, mid, u, d);
    else update(x<<1|1, mid+1, r, u, d);
}
int query(int x, int l, int r,int ql, int qr){
    if (ql <= l && r <= qr) return st[x];
    int mid = (l+r)/2;
    int ret = 0;
    if (ql <= mid) ret = max(ret, query(x<<1, l, mid, ql, qr));
    if (mid < qr) ret = max(ret, query(x<<1|1, mid+1, r,  ql, qr));
    return ret;
}

int main() {
    cin >> n >> k;
    for (int i = 0, a, ret; i < n; i++){
        cin >> a;
        ret = query(1, 1, 300000, a-k, a+k);
        ret++;
        ans = max(ans, ret);
        update(1, 1, 300000,  a, ret);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 7736
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<limits>
#include<deque>
#include<string>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>

using namespace std;

int main(){
	int n; cin >> n;
	int t; cin >> t;
	long long int sum = 0;
	int tt[n];
	for (int i = 0; i < n; i++) {
		cin >> tt[i];
	}
  
    if(n==1){cout<<t<<endl;return 0;}
    
	for (int i = 1; i < n; i++) {
		if (t >= tt[i] - tt[i - 1]) { sum += (tt[i] - tt[i - 1]); }
		else { sum += t; }
	}
    sum+=t;

	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 1024
N, K = map(int, input().split())
has_snack = set()
for i in range(K):
    d = int(input())
    A = list(map(int, input().split()))
    for a in A:
        has_snack.add(a)
ans = 0
for i in range(1, N + 1):
    if i not in has_snack:
        ans += 1
        
print(ans)

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

int main(){
    int n;
    cin >> n;
    int t = 0, x = 0, y = 0;
    bool ok = true;
    for(int i=0;i<n;++i){
        int nt, nx, ny;
        cin >> nt >> nx >> ny;
        if(ok){
            int d = abs(nx-x) + abs(ny-y);
            if(nt - t < d || (nt-t)%2 != d%2){
                ok = false;
            }
            t = nt;
            x = nx;
            y = ny;
        }
    }

    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

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

const int INTINF = int(1e9) + 1;
const LL LLINFLL = LL(1e18) + 1;
#define pow10(n) int(1e##n + n)
const LL mod = 1e9 + 7;

void solve()
{
    const int d = 62;
    int N;
    cin >> N;
    vector<LL> A(N);

    REP0 (i, N)
    {
        cin >> A[i];
    }

    LL ans = 0;

    REP0 (j, d)
    {
        LL d0 = 0;
        LL d1 = 0;
        REP0 (i, N)
        {
            if (A[i] & (1LL << j))
                d1++;
            else
                d0++;
        }
        ans += ((d0 * d1) % mod) * ((1LL << j) % mod);
        ans %= mod;
    }

    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <vector>
using namespace std;
struct edge{int to,l;};
vector<vector<edge>>G;

// 二部グラフ判定
vector<int> color;
void dfs(int v, int d ) {
    for (auto x : G[v]) {
        // 隣接頂点がすでに色確定していた場合
        if (color[x.to] != -1) {
             // 同じ色が隣接したらダメ
            continue;
        }

        // 隣接頂点の色を変えて、再帰的に探索 (一回でも false が返ってきたら false)
        if((d+x.l)%2==1){
            color[x.to]=1;
            dfs(x.to,d+x.l);
        }
        else if((d+x.l)%2==0){
            color[x.to]=0;
            dfs(x.to,d+x.l);
        }
    }
}

int main() {
    // 頂点数と辺数
    int N; cin >> N ;

    // グラフ入力受取
    G.resize(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b, l;
        cin >> a >> b >> l;
        a--;b--;
        G[a].push_back(edge{b,l%2});
        G[b].push_back(edge{a,l%2});
    }

    // 探索
    color.assign(N, -1);
    color[0]=0;
    dfs(0,0);
    for(int i=0;i<N;++i)cout<<color[i]<<endl;
}


Measured memory_bytes: 7424
n, m = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)])

i = 0 # 今何本かったか
price = 0 # 合計いくらか
for a, b in ab:
    price += a * min(b, m-i)
    i += min(b, m-i)
    if i == m:
        print(price)
        exit()

Measured memory_bytes: 17752
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll a[100000+10];
ll b[100000+10];
ll c[100000+10];
ll dp[100000+10][3];

int main(){
int n;
cin >> n;

for(int i=0; i<n; i++){
cin >> a[i] >> b[i] >> c[i];
}
dp[0][0] = a[0];
dp[0][1] = b[0];
dp[0][2] = c[0];
for(int i=1; i<n; i++){
    dp[i][0] = a[i] + max(dp[i-1][1], dp[i-1][2]);
    dp[i][1] = b[i] + max(dp[i-1][0], dp[i-1][2]);
    dp[i][2] = c[i] + max(dp[i-1][0], dp[i-1][1]);
}
cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
return 0;
}


Measured memory_bytes: 8168
#include <stdio.h>

int main(void)
{
	int m, f, r;
	
	while (scanf("%d %d %d", &m, &f, &r), m != -1 || f != -1 || r != -1){
		if (m == -1 || f == -1){
			printf("F\n");
		}
		else if (80 <= m + f){
			printf("A\n");
		}
		else if (65 <= m + f && m + f < 80){
			printf("B\n");
		}
		else if (50 <= m + f && m + f < 65 || 50 <= r){
			printf("C\n");
		}
		else if (30 <= m + f && m + f < 50){
			printf("D\n");
		}
		else if (m + f < 30){
			printf("F\n");
		}
	}
	return (0);
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5;

int readInt ()
{
    bool minus = false;
    int result = 0;
    char ch;
    ch = getchar();
    while (true)
    {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus = true;
    else result = ch-'0';
    while (true)
    {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}
main() {
    int n = readInt();
    cout << n * (n - 1) / 2;
}


Measured memory_bytes: 256
n,m,c = map(int,input().split())
b=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(n)]
count=0
t=c
for i in range(n):
    for j in range(m):
        t += a[i][j]*b[j]
    if t > 0:
        count += 1
    t=c

print(count)


Measured memory_bytes: 38420
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

//gcd,lcm,べき,二進展開
//組み合わせ、mod計算
//最短路問題、bit、union find

///////////////////////////



int main() {
	ll H;
	ll W;
	ll N;
	cin >> H >> W >> N;

	ll x = max(H, W);

	cout << (N - 1) / x + 1;

	system("PAUSE");

}


Measured memory_bytes: 504
class TreeNode:
    def __init__(self, nodeid):
        self.nodeid = nodeid
        self.parent = None
        self.sibling = None
        self.child = None
        self.depth = 0

    def node_type(self):
        if self.parent is None:
            return 'root'
        elif self.child is None:
            return 'leaf'
        else:
            return 'internal node'

    def parent_nodeid(self):
        if self.parent is None:
            return -1
        else:
            return self.parent.nodeid

    def child_nodeids(self):
        if self.child is not None:
            yield self.child.nodeid
            yield from self.child.sibling_nodeids()

    def sibling_nodeids(self):
        s = self.sibling
        stack = []
        while s is not None:
            stack.append(s.nodeid)
            s = s.sibling
        while len(stack) > 0:
            yield stack.pop()

    def get_depth(self):
        if self.node_type() != 'root' and self.depth == 0:
            self.depth = self.parent.get_depth() + 1

        return self.depth

    def add_child(self, node):
        if self.child is None:
            self.child = node
            self.child.parent = self
        else:
            self.child.add_sibling(node)

    def add_sibling(self, node):
        node.parent = self.parent
        node.sibling = self.sibling
        self.sibling = node

    def __str__(self):
        return ('node {}: parent = {}, depth = {}, {}, [{}]'.format(
                self.nodeid, self.parent_nodeid(), self.get_depth(),
                self.node_type(),
                ", ".join([str(i) for i in self.child_nodeids()])))


class Tree:
    def __init__(self):
        self.nodes = {}

    def node(self, nodeid):
        if nodeid not in self.nodes:
            self.nodes[nodeid] = TreeNode(nodeid)

        return self.nodes[nodeid]

    def sorted_nodes(self):
        for nodeid in sorted(self.nodes.keys()):
            yield self.nodes[nodeid]


def run():
    c = int(input())
    tree = Tree()

    for _ in range(c):
        nodeid, deg, *cs = [int(i) for i in input().split()]
        node = tree.node(nodeid)
        for c in cs:
            node.add_child(tree.node(c))

    for node in tree.sorted_nodes():
        print(node)


if __name__ == '__main__':
    run()



Measured memory_bytes: 38532
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1000000005LL
#define MOD 1000000007

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

ll n,m;
ll A[SIZE*2],B[SIZE*2];
void imosu(ll l,ll r){
	if(l>r)return;
	A[l]++;
	A[r+1]--;
	B[r+1] += r+1-l;
}

int main()
{
	cin >> n >> m;
	ll a,b;
	cin >> b;
	ll X = 0;
	rep(i,1,n){
		a = b%m;
		cin >> b;
		if(b<a)b+=m;
		imosu(a+2,b);
		X += b-a;
	}
	rep(i,1,2*m+2){
		A[i] += A[i-1];
	}
	rep(i,1,2*m+2){
		A[i] -= B[i];
	}
	rep(i,1,2*m+2){
		A[i] += A[i-1];
	}
	ll Y = 0;
	rep(i,1,m+1){
		A[i] += A[i+m];
		Y = max(Y,A[i]);
	}

	//rep(i,1,m+1) cout << A[i] << endl;
	cout << X-Y << endl;

	return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  string s;
  cin>>s;
  cout<<"ABC"<<s<<endl;

  return 0;
}




Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  string S;
  get(S);
  sort(ALL(S));
  print(S == "abc" ? "Yes" : "No");
  return 0;
}

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

int main()
{
    int n;
    cin>>n;
    int s=0;
    for(int i=0;i<n;i++)
    {   long long k;
        cin>>k;
        s+=k;
    }
    cout<<s-n<<endl;

    return 0;

}


Measured memory_bytes: 3560
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

int main() {
	complex<long double>cmpmp;
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	//cout << fixed << setprecision(10);
	int n, m, t;
	cin >> n >> m >> t;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int res = 0;
	res += max(a[0] - m, 0);
	for (int i = 0; i < n - 1; i++) {
		res += max((a[i + 1] - a[i]) - 2 * m, 0);
	}
	res += max((t - a.back()) - m, 0);
	cout << res << endl;
}



Measured memory_bytes: 3104
#!/usr/bin/env python3
import sys


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    MOD = 2019
    L,R = [int(s) for s in input().split()]
    if R-L+1 >= MOD:
        print(0)
        sys.exit()

    min_rmdr = MOD

    for i in range(L,R):
        for j in range(L+1,R+1):
            if (i * j) % MOD < min_rmdr:
                min_rmdr = (i * j) % MOD
    
    print(min_rmdr)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
def solve():
    from collections import deque
    S = input()
    s = deque(S)
    Q = int(input())
    reverse = False
    for i in range(Q):
        T = input().split()
        if T[0] == '1':
            if reverse:
                reverse = False
            else:
                reverse = True
        else:
            if T[1] == '1' and not reverse:
                s.appendleft(T[2])
            elif T[1] == '1' and reverse:
                s.append(T[2])
            elif T[1] == '2' and not reverse:
                s.append(T[2])
            else:
                s.appendleft(T[2])
    if reverse:
        print(''.join(s)[::-1])
    else:
        print(''.join(s))

if __name__ == "__main__":
    solve()

Measured memory_bytes: 14428
#include<bits/stdc++.h>
using namespace std;
long long read()
{
	char ch=getchar();long long x=0,ff=1;
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*ff;
}
void write(long long aa)
{
	if(aa<0) putchar('-'),aa=-aa;
	if(aa>9) write(aa/10);
	putchar(aa%10+'0');
	return;
}
const long long inf=1000000005;
const long long mod=1e9+7;
long long n,X,Y,sum,ans;
long long jl[200005],mn[200005],val[200005];
long long fac[200005],ny[200005],col[200005];
long long ksm(long long aa,long long bb)
{
	long long ans=1;
	while(bb)
	{
		if(bb&1) ans=(ans*aa)%mod;
		bb>>=1;
		aa=(aa*aa)%mod;
	}
	return ans;
}
long long C(long long aa,long long bb)
{
	return fac[bb]*ny[aa]%mod*ny[bb-aa]%mod;
}
int main()
{
	n=read(),X=read(),Y=read();
	fac[0]=1;
	for(long long i=1;i<=n;++i)
	{
		col[i]=read(),val[i]=read();
		jl[col[i]]++;
		mn[i]=inf;
		fac[i]=(fac[i-1]*i)%mod;
	}
	ny[n]=ksm(fac[n],mod-2);
	for(long long i=n;i>=1;--i) ny[i-1]=(ny[i]*i)%mod;
	for(long long i=1;i<=n;++i) mn[col[i]]=min(mn[col[i]],val[i]);
	long long mx=0,mxx=0;
	for(long long i=1;i<=n;++i)
	if(mn[i]!=inf)
	{
		if(!mx||mn[i]<mn[mx]) mx=i;
		else if(!mxx||mn[i]<mn[mxx]) mxx=i;
	}
	for(long long i=1;i<=n;++i)
	{
		if(mn[col[i]]!=val[i]&&mn[col[i]]+val[i]<=X) continue;
		if(col[i]==mx&&val[i]+mn[mxx]<=Y) continue;
		if(col[i]!=mx&&val[i]+mn[mx]<=Y) continue;
		jl[col[i]]--;
	}
	ans=1;
	sum=jl[mx];
	for(long long i=1;i<=n;++i)
	if(i!=mx&&mn[i]+mn[mx]<=Y) {sum+=jl[i];ans=(ans*C(jl[i],sum))%mod;}
	write(ans);
	return 0;
} 

Measured memory_bytes: 9600
/* This code is written by 18to_nhanh */
#define Tourist "169F"
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORs(i,a,b) for(int i=a;i<b;i++)
#define _FOR(i,a,b) for(int i=a;i>=b;i--)
#define _FORs(i,a,b) for(int i=a;i>b;i--)
using namespace std;
const int maxn = 3e3;
const int INF = 1e9;
const int MOD = 998244353;
const int base = 31;
const int LOG = 20;
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
int n,s;
int a[maxn+5];
int dp[maxn+5][maxn+5];
void init(){
//    freopen(Tourist".inp","r",stdin);
//    freopen(Tourist".out","w",stdout);
}
void Time_Decreasing(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}
void enter(){
    scanf("%d %d",&n,&s);
    FOR(i,1,n) scanf("%d",&a[i]);
}
void solve(){
    dp[0][0] = 1;
    FOR(i,1,n){
         FOR(j,0,s){
             dp[i][j] = (dp[i][j] + 2 * dp[i-1][j]) % MOD;
             if(j - a[i] >= 0){
                dp[i][j] = (dp[i][j] + dp[i-1][j-a[i]]) % MOD;
             }
         }
    }
    printf("%d\n",dp[n][s]);
//    FOR(i,0,n){
//        FOR(j,0,s){
//            printf("%d %d %d\n",i,j,dp[i][j]);
//        }
//    }
}
int main(){
    init();
    Time_Decreasing();
    enter();
    solve();
}


Measured memory_bytes: 38988
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
    int A,B,H,M;
    scanf("%d",&A); scanf("%d",&B);
    scanf("%d",&H); scanf("%d",&M);
    double lx,ly,sx,sy;
    double theta;
    //時針の方の端点の座標
    theta = (H*30 + 0.5*M)*M_PI/180;
    lx = A*sin(theta);
    ly = A*cos(theta);
    //printf("theta=%f lx=%f ly=%f\n",theta,lx,ly);
    //分針の方の端点の座標
    theta = M*6*M_PI/180;
    sx = B*sin(theta);
    sy = B*cos(theta);

    printf("%.9f\n",sqrt((lx-sx)*(lx-sx)+(ly-sy)*(ly-sy)));
    //printf("theta=%f sx=%f sy=%f\n",theta,sx,sy);
    
    return 0;
}

Measured memory_bytes: 2468
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1LL << 30;

int main(){
  ll N, M;
  cin >> N >> M;
  ll time = (N-M) * 100LL + M * 1900LL;
  cout << time * pow(2, M) << endl;
}

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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define ALL(a) a.begin(),a.end()
#define INIT(a,b) memset(a,b,sizeof(a))
using lint = long long int;

lint pow5(lint x) { return x * x * x * x * x; }

int main() {
    lint X;
    cin >> X;

    for_(a,0,1000) for_(b,-1000,1000) {
        lint x = pow5(a) - pow5(b);
        if (x == X) {
            cout << a << " " << b << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

const int INF = 1<<29;        // 十分大きい値にする, INT_MAX にしないのはオーバーフロー対策
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; }

// 入力
int N, W;

// DPテーブル
int dp[110][10010];

void printdp(vector<int> a, vector<int> b) {
    cout << "--------------" << endl;
    cout << "      ";
    REP(i, W+1) {
        cout << i <<  "   ";
    }   
    cout << endl;
    REP(i, N + 1) {
        cout << a[i-1] << "," << b[i-1] << ":";
        REP(j, W + 1) {
            cout << setw(3) <<  (dp[i][j] == INF ? 9 : dp[i][j]) << " ";
        }
        cout << endl;
    }
}


int main() {
    cin >> N >> W;
    vector<int> VS(N), WS(N);
    for (int i = 0; i < N; ++i) cin >> VS[i] >> WS[i];
    
    REP(i, N+1) REP(j, W+1) {
        dp[i][j] = 0;
    }

    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if(j >= WS[i]) {
                dp[i+1][j] = max(dp[i][j-WS[i]]+VS[i], max(dp[i+1][j-WS[i]]+VS[i],dp[i][j]));
            } else {
                dp[i+1][j] = dp[i][j];
            }
        }

        // printdp(VS, WS);
    }
    cout << dp[N][W] << endl;
}


Measured memory_bytes: 7052
n = int(input())
b_list = list(map(int, input().split()))

pre_b = 0
output = []
for index, b in enumerate(b_list):
    if index == 0:
        output.append(b)
    else:
        if pre_b <= b:
            output.append(pre_b)
        else:
            output.append(b)
    pre_b = b
output.append(b_list[-1])
print(sum(output))

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

int main() {
  string T;
  cin >> T;
  for (int i = 0; i < T.size(); i++) {
    if (T.at(i) == '?') {
      T.at(i) = 'D';
    }
  }
  cout << T << endl;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  cin >> N >> K;
  vector <int> vec(N);
  int a = 0;
  for(int i = 0; i < N; i++){
    cin >> vec.at(i);
    if( vec.at(i) >= K){
      a++;
    }
  }
  cout << a << endl;
}
  
 


Measured memory_bytes: 640
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		char[] ca=new char[N];
		for(int i=0;i<N;i++){
			if(S[i]=='0'){
				if(D>0){
					ca[i]='1';
					D--;
				}else{
					ca[i]='0';
				}
			}
		}
		for(int i=N-1;i>=0;i--){
			if(S[i]=='1'){
				if(D>0){
					ca[i]='0';
					D--;
				}else{
					ca[i]='1';
				}
			}
		}
		Console.WriteLine(new String(ca));
		
		
		
		
	}
	int N;
	String S;
	int D;
	public Sol(){
		N=ri();
		S=rs();
		D=ri();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

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

#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 100005
#define ALL(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)


using namespace std;


int32_t main()
{
    IOS;

    int tt=1;
    //cin>>tt;
    while(tt--)
    {
        int n; cin>>n;
        int arr[n];
        int pre[n];
        int post[n];
        int ans = 0;
        for (int i = 0; i < n; i++)
		{
			cin>>arr[i];
			ans = __gcd(ans,arr[i]);
		}
		pre[0] = arr[0];
		for (int i = 1; i < n; i++)
		{
			pre[i] = __gcd(arr[i],pre[i-1]);
		}
		post[n-1] = arr[n-1];
		for (int i = n-2; i>=0; i--)
		{
			post[i] = __gcd(arr[i],post[i+1]);
		}
		
		for (int i = 1; i < n - 1; i++)
		{
			ans = max(ans,__gcd(pre[i-1],post[i+1]));
		}
		ans = max(ans,post[1]);
		ans = max(ans,pre[n-2]);
		cout<<ans<<endl;
		
    }
    return 0;

}


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

const ll INF = 1LL << 60;

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  REP(i, 0, N) cin >> A[i];
  REP(i, 0, N) cin >> B[i];

  map<ll, bool> mp;
  REP(i, 1, 52) mp[i] = true;

  for(ll t = 51; t > 0; t--) {
    mp[t] = false;
    vector< vector<ll> > dist(51, vector<ll>(51, INF));
    REP(i, 0, 51) dist[i][i] = 0;
    REP(i, 0, 51) REP(j, 1, 51) if(mp[j]) dist[i][i % j] = 1LL << j;
    REP(k, 0, 51) REP(i, 0, 51) REP(j, 0, 51) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    bool ok = true;
    REP(i, 0, N) ok = ok && dist[A[i]][B[i]] < INF;
    if(!ok) mp[t] = true;
  }

  ll ans = 0;
  if(!mp[51]) { REP(i, 1, 51) if(mp[i]) ans += 1LL << i; }
  else ans = -1;
  cout << ans << endl;
}


Measured memory_bytes: 256
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()

N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

preds = dict(bfs_predecessors(G,source=1))

if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])

Measured memory_bytes: 229496
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

template <typename TYPE>
void print_vec(const vector<TYPE>& v, int num=0){
  if(num == 0) num = (int)v.size();
	for(int i=0; i<num; i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { 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;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main(){
	int X, Y;
	cin >> X >> Y;
	if( (X+Y) % 3 != 0){
		cout << 0 << endl;
		return 0;
	}
	
	int n = (X+Y) / 3;
	X -= n; 	Y -= n;
	combination comv(X+Y);
	cout << comv(X+Y, X) << endl;

	// 以下wrong answer解答
	// if(X<Y) swap(X, Y);
	// int a = X / 2;
	// X -= a * 2;
	// Y -= a * 1;
	// if(Y<0){
	// 	cout << 0 << endl;
	// 	return 0;
	// }
	// int b = Y / 2;
	// // X -= b * 1;
	// // Y -= b * 2;
	
	// cout << " a: " << a << " b: " << b << endl;
	// combination comv(a+b+1);
	// cout << comv(a+b, a) << endl;

	return 0;
}



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

#define ll long long int
#define endl '\n'
#define inf 1e18
ll ar[100005];
ll dp[100005];
void testCase()
{
    
   // ll t; cin>>t; while(t--)
    {
      ll n;
      cin>>n;
      ll ar[n];
      for(int i=1;i<=n;i++)
      cin>>ar[i];

      for(int i=1;i<=n;i++)
      dp[i]=INT_MAX;

      dp[1]=0;

      for(int i=2;i<=n;i++)
      {
          if(i>2)
          {
              dp[i]=dp[i-2]+abs(ar[i]-ar[i-2]);
          }
          dp[i]=min(dp[i],dp[i-1]+abs(ar[i]-ar[i-1]));
      }
      cout<<dp[n]<<endl;
    }       
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    testCase();
    return 0;
}

Measured memory_bytes: 5168