akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    vector<vector<T>>(h,vector<T>(w))
#define VVI(T,h,w,i) vector<vector<T>>(h,vector<T>(w,i))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
    /* S(x)=x(1+x)/2
       S([x,y))=S(y-1)-S(x-1)
               =(y-1)y/2-(x-1)x/2
               ={(y-1)y-(x-1)x}/2
       S([x,x+a))={(x+a-1)(x+a)-(x-1)x}/2
                 =a(2x+a-1)/2
       b=a(2x+a-1)/2
       2ax-a-2b+a^2=0
       x=(a+2b-a^2)/2a
    */
    while (true) {
        ll b = in();
        if (b == 0)break;
        for (ll a = static_cast<ll>(sqrt(b)) * 2;; --a) {
            if ((a + 2 * b - a * a) % (2 * a) == 0) {
                ll x = (a + 2 * b - a * a) / (2 * a);
                if (x >= 1) {
                    cout << x << ' ' << a << endl;
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string.h>
using namespace std;
#define pb push_back
#define all(v) v. begin(),v. end()
#define  rep(i,n,v) for(i=n;i<v;i++)
#define per(i,n,v) for(i=n;i>v;i--)
#define ff first 
#define ss second 
#define pp pair<ll,ll>
#define ll  long long
#define endl '\n'
void solve()
{
  ll n, a,m=0,b=1, c,k=0, i, j,l=1e9+7;
  string s, r, y;
  cin>>n;
  vector<ll>v(1000500);
  rep(i,1,103)
  rep(j,1,103)
  rep(k,1,103)
  {
    b=i*i+j*j+k*k+i*j+i*k+j*k;
    v[--b]++;
  }
  rep(i,0,n) cout<<v[i]<<endl;
}
int main()
{
 ios_base::sync_with_stdio(false);
  cin. tie(0);cout. tie(0);
    ll t=1;
   //cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

Measured memory_bytes: 11032
#1問目
N = input()
if int(N[-1]) == 2 or int(N[-1])==4 or int(N[-1])==5 or int(N[-1])==7 or int(N[-1])==9:
    print("hon")
elif int(N[-1])==0 or int(N[-1])==1 or int(N[-1])==6 or int(N[-1])==8:
    print("pon")
else:
    print("bon")

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

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

  int l = S.size();
  int Ans = 1000;

  for ( int i=0; i<=l-3; i++ ) {
    int num = ( S[i]-'0' )*100 + ( S[i+1]-'0' )*10 + ( S[i+2]-'0');
    Ans = min( Ans, abs( num-753 ) );
  }

  cout << Ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <bitset>
#include <utility>
#include <cstring>
#include <numeric>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pair<int,int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
#define rep(i,n) for(int i=0;i<n;i++)
#define repll(i,n) for(long long int i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define P 1000000007
#define STI(s) atoi(s.c_str())//string to int
#define mp(p,q) make_pair(p,q)
#define Sort(a) sort(a.begin(),a.end())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
template <typename T_char>
char ToUpper (char cX) { return toupper(cX); }
//g++ -std=c++1z temp.cpp
//./a.exe
ll digit(ll a){
    ll count = 0;
    for (ll i = 0; i < a; i++)
    {   if (a == 0)
        {
            break;
        }else
        {
            a = a/10;
            count++;
        }
    }
    return count;
}

uintmax_t comb(unsigned int n, unsigned int r) {
  if ( r * 2 > n ) r = n - r;
  uintmax_t dividend = 1;
  uintmax_t divisor  = 1;
  for ( unsigned int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}
//桁数のカウント
//pow(x,n) == x^n
//sum = accumulate(v.begin(),v.end(),0);
using Graph = vector<vector<int>>;




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

string s,t;
cin >> s >> t;
bool flag = true;


rep(i,s.length()){
  if(s[i] != t[i]) flag = false;
}

if(flag == true) cout << "Yes" << endl;
else cout << "No" << endl;


//////////////////////////////////////////////////////
return 0;}


Measured memory_bytes: 3612
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
#define ll long long
#define INFTY 1 << 21
ll min(ll a, ll b) { return b < a ? b : a; }
ll max(ll a, ll b) { return b < a ? a : b; }

int main() {
  int N;
  cin >> N;
  int ans = pow(N, 3);
  cout << ans << endl;
}


Measured memory_bytes: 256
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

use rand::{thread_rng, Rng};

fn calc(v: &Vec<Vec<isize>>, plan: &Vec<usize>, c: &Vec<isize>) -> isize {
    let mut last = vec![0; 26];
    let mut res = 0_isize;
    for (i, &x) in plan.iter().enumerate() {
        res += v[i][x];
        last[x] = i as isize + 1;
        for (j, &y) in last.iter().enumerate() {
            res -= c[j] * (i as isize + 1 - y);
        }
    }

    res
}

fn main() {
    input! {
        d:usize,
        c:[isize;26]
    }
    let mut v = vec![];
    for _ in 0..d {
        input! {
            buf:[isize;26]
        }
        v.push(buf);
    }
    let mut rng = rand::thread_rng();
    let mut plan = vec![0; d];
    let mut prev_score = calc(&v, &plan, &c);
    for _ in 0..10000 {
        let idx = rng.gen_range(0, d);
        let to = rng.gen_range(0, 26);
        let from = plan[idx];
        plan[idx] = to;
        let next_score = calc(&v, &plan, &c);
        if next_score > prev_score {
            prev_score = next_score;
        } else {
            plan[idx] = from;
        }
    }
    for i in plan {
        println!("{}", i + 1);
    }
}


Measured memory_bytes: 2756
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#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() {
    int n,k;
    cin >> n >> k;

    double ans = 0;
    double sum = 0;
    queue<double> q;
    rep(i,n){
        double p;
        cin >> p;
        while (q.size() >= k) {
            sum -= q.front();
            q.pop();
        }
        double x = (1 + p)/2;
        sum += x;
        q.push(x);
        ans = max(ans,sum);
    }
    printf("%.10f\n",ans);
}


Measured memory_bytes: 1792
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

ll intceil(ll a, ll b) {
   if (a == 0) return 0;
   if (b == 0) return -1;
   ll ret = a / b;
   if (a % b != 0) ret += 1;
   return ret;
}

const int NMAX = 100010;
int h[NMAX];
int N, A, B, C;

bool isOK(int n) {
   ll cnt = 0;
   for (int i = 0; i < N; i++) {
      int tmp = h[i] - n * B;
      if (tmp <= 0) continue;
      cnt += intceil(tmp, C);
   }
   if (cnt <= n) return true;
   else return false;
}

int main() {
   cin >> N >> A >> B;
   int hmax = 0;
   for (int i = 0; i < N; i++) {
      cin >> h[i];
      chmax(hmax, h[i]);
   }
   C = A - B;

   int ng = -1;
   int ok = intceil(hmax, B);

   while (abs(ok - ng) > 1) {
      int mid = (ok + ng) / 2;
      
      if (isOK(mid)) ok = mid;
      else ng = mid;
   }
   cout << ok << endl;
   return 0;
}


Measured memory_bytes: 640
package main

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

func main() {
	s := ScanWord()

	r := isPalindrom(s) && isPalindrom(s[:(len(s)-1)/2]) && isPalindrom(s[(len(s)-1+3)/2:])
	if r {
		P("Yes")
	} else {
		P("No")
	}
}

func isPalindrom(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}

/*********************** I/O ***********************/

var in *bufio.Scanner
var P func(a ...interface{}) (n int, err error)

func init() {
	P = fmt.Println

	in = bufio.NewScanner(os.Stdin)
	in.Buffer(make([]byte, 1024), int(1e+9))
	in.Split(bufio.ScanWords)
}

func ScanWord() string { in.Scan(); return in.Text() }
func ScanInt() int     { i, _ := strconv.Atoi(ScanWord()); return i }
func ScanStringSlice(n int) []string {
	s := make([]string, n)
	for i := 0; i < n; i++ {
		s[i] = ScanWord()
	}
	return s
}
func ScanIntSlice(n int) []int {
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = ScanInt()
	}
	return arr
}

/*********************** Utils ***********************/

func S(v interface{}) string { return fmt.Sprintf("%v", v) }
func MnMx(args ...int) (int, int) {
	minVal, maxVal := int(math.MaxInt32), int(math.MinInt32)
	for _, v := range args {
		if v < minVal {
			minVal = v
		}
		if v > maxVal {
			maxVal = v
		}
	}
	return minVal, maxVal
}
func Mn(args ...int) int { mn, _ := MnMx(args...); return mn }
func Mx(args ...int) int { _, mx := MnMx(args...); return mx }
func LCM(a, b int) int   { return a / GCD(a, b) * b }
func GCD(a, b int) int {
	if a == 0 {
		return b
	}
	return GCD(b%a, a)
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n,m;
    cin>>n>>m;
    vector<P> p(n);
    rep(i,n){
        cin>>p[i].first>>p[i].second;
    }
    sort(btoe(p));
    ll ans=0;
    int a=0;
    while(m>0){
        if(p[a].second==0) a++;
        ans+=p[a].first; p[a].second--; m--;
    }
    cout<<ans<<endl;
}

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  int i = 1;
  while (a * i <= a * b) {
    if ((a * i) % b == c) {
      cout << "YES" << endl;
      return 0;
    }
    i++;
  }
  cout << "NO" << endl;
}

Measured memory_bytes: 256
def q3():
    import itertools
    l1 = input().split()
    D = int(l1[0])  # 問題数
    G = int(l1[1])  # 総合スコア

    P = []  # 各スコアごとの問題数
    C = []  # コンプリートボーナス
    for i in range(D):
        l = input().split()
        P.append(int(l[0]))
        C.append(int(l[1]))

    # コンプリートするかしないかの組み合わせ作成 2^D個, する:1 しない:0
    for i in range(D):
        li = list(itertools.product([1, 0], repeat=D))

    ans = float('INF')
    for e in li:
        tmp_sum = 0  # 総得点
        tmp_ans = 0  # 総正解数

        # コンプリートした問題だけを先に足しておく
        for i, flag in enumerate(e):
            tmp_sum += (P[i]*(i+1)*100 + C[i]) * flag
            tmp_ans += P[i]*flag

        # print(tmp_sum, tmp_ans, e)

        # コンプリートボーナスだけで目標点数Gを超えているか？
        if tmp_sum >= G:
            ans = min(ans, tmp_ans)  # ans更新
            continue

        for i in range(D-1, -1, -1):
            if e[i] == 1:
                continue
            for _ in range(0, P[i]):
                tmp_sum += (i+1)*100
                tmp_ans += 1
                # print(i, tmp_sum)

                if tmp_sum >= G:
                    ans = min(ans, tmp_ans)  # ans更新
                    break
            if tmp_sum >= G:
                break

    return ans

if __name__ == "__main__":
    print(q3())


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

string board[1010];
bool visited[1010][1010];
li dx[] = { -1, 1, 0, 0};
li dy[] = {0, 0, -1, 1};

int main() {
    li h, w;
    cin >> h >> w;
    rep(i, h) {
        cin >> board[i];
    }

    queue<pair<li, PI>> q;
    rep(i, h) {
        rep(j, w) {
            if (board[i][j] == '#') {
                q.push({0, {i, j}});
            }
        }
    }

    li res = 0;
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        if (visited[now.S.F][now.S.S]) {
            continue;
        }
        visited[now.S.F][now.S.S] = true;
        res = max(res, now.F);

        rep(i, 4) {
            PI next{now.S.F + dy[i], now.S.S + dx[i]};
            if (min(next.F, next.S) >= 0 && next.F < h && next.S < w) {
                q.push({now.F + 1, next});
            }
        }
    }

    cout << res << endl;


    return 0;
}

Measured memory_bytes: 99512
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	var a,b int
	var k string
	var cnt int = 0
	fmt.Scan(&a,&b)

	for i:= a; i <= b; i++ {
		k = strconv.Itoa(i)
		kk := strings.Split(k, "")
		if kk[0] == kk[4] && kk[1] == kk[3] {
			cnt++
		}
	}

	fmt.Println(cnt)
}

Measured memory_bytes: 6264
//https://vjudge.net/contest/233220#problem/D

#include<bits/stdc++.h>
#define mod 998244353LL
#define powmod 998244351LL
using namespace std;
long long f[300001];
int N,A,B;
long long K,Ans = 0;
void factorial()
{
   f[0] = 1LL;
   for(int i = 1;i <= 300000;i++)
   {
      f[i] = (long long)(f[i - 1] * i * 1LL)% mod;
   }
}
long long power(int u,int v)
{
   if(v == 0) return 1LL;
   if(v == 1) return u*1LL;
   long long X = power(u,v/2) % mod;
   if(v % 2 == 0) return X * X % mod;
   else return ((X * X) % mod * u) % mod;
}
long long C(int k,int n)
{
   //printf("C(%lld,%lld) = %lld\n",k,n,nume*power(deno,powmod) % mod);n
   long long _n = f[n];
   long long _k = f[k];
   long long _t = f[n - k];
   long long deno = power(_k,powmod) * power(_t,powmod) % mod;
   long long nume = _n;
   return nume * deno % mod;
}
signed main()
{
    factorial();
   cin >> N >> A >> B >> K;
   //cout << "Snap!";
   for(int i = 0;i < N + 1;i++)
   {
      if((K - A*i) % B == 0LL)
      {
         long long j = (K - A*i)/B;
         if(j > N || j < 0LL) continue;
         Ans += C(i,N) * C(j,N) % mod;
      }
   }
   cout << Ans % mod;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdouble;


int main() {
  ll n;
  cin >> n;
  vector<ll> A(n);

  for(int i =0; i<n; i++){
    cin >> A.at(i);
  }

  sort(A.begin(),A.end());

  bool flag =false;
  for(int i =0; i<n-1; i++){
    if(A.at(i)==A.at(i+1)){
      flag = true;
    }
  }

  if(flag == true){
    cout << "NO" << endl;
  }else{
    cout << "YES" << endl;
  }
  return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define MOD         1000000007
#define hell        1000000007
#define N	    400001
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rev(i,a,b)  for(int i=a;i>=b;i--)
#define ll          long long
#define bg(i)       i.begin()
#define fset(it,s)   for(auto it = s.begin(); it != s.end(); it++)


#define track(x)                cerr<<#x<<": "<<x<<endl
#define track2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define track3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define track4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl

#define ed(i)       i.end()
#define mem(a)	    memset(a, 0, sizeof(a))
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1LL) {if (k & 1LL) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
void self_max(int &a, int &b) {a = max(a, b); } 
void self_min(int &a, int &b) {a = min(a, b); }
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ll dp[N];
const int INF = 1e9 + 5;
void solve(){
	int n, W;
	cin>>n>>W;
	vi v(n), w(n);
	rep(i,0,n) cin>>w[i]>>v[i];
	int sum_value = 0;
	for(int i : v)
		sum_value += i;

	vector<ll> dp(sum_value + 1, INF);
	dp[0] = 0;
	//dp[i]  what is the minimum weight possible for this value
	rep(i,0,n) {
		rev(j, sum_value, 0) {
			if(j - v[i] < 0)
				break;
			dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	int ans = 0;
	rep(i,0,sum_value+1) {
		if(dp[i]  <= W) 
			self_max(ans, i);
	}
	cout<<ans<<endl;
}
int main() {
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin>>t;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>
#include <sstream>
#include <bitset>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007
#define MOD ((int)1e9+7)
//static const long double pi = 3.1415926535897932;

using namespace std;
using ll = long long int;
using ull = unsigned long long;

char toSmall(char c) { // 大文字を小文字へ
	return (c + 0x20);
}

char toLarge(char c) { // 小文字を大文字へ
	return (c - 0x20);
}

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

struct Combination {
	const int num=51e4;			//要素数
	const int mod=1e9+7;
	vector<ll> fact,inv,finv; //階乗,逆元,逆元の階乗.
	
	Combination():fact(num),inv(num),finv(num){
		fact[0]=fact[1]=1;
		inv[1]=1;
		finv[0]=finv[1]=1;
		for(int i=2;i<num;++i){
			fact[i]=fact[i-1]*i%mod;
			inv[i]=mod-inv[mod%i]*(mod/i)%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	
	int nCk(int n,int k){
		if(n<k) return 0;
		if(n<0 or k<0) return 0;
		return fact[n]*(finv[k]*finv[n-k]%mod)%mod;
	}
	int big_nCk(int n,int k){ //nが大きいとき
		ll res=1LL;
		for (int i = 0; i < k; i++) {
			res=res*(n-i)%mod;
		}
		res = res*finv[k]%mod;
		return res;
	}
	int nHk(int n,int k){return nCk(n+k-1,n-1);}//重複組み合わせ.
};

vector<string> split(const string& src, const char* delim = ",") { //カンマ区切り
	vector<string> vec;
	string::size_type len = src.length();

	for (string::size_type i = 0, n; i < len; i = n + 1) {
		n = src.find_first_of(delim, i);
		if (n == string::npos) {
			n = len;
		}
		vec.push_back(src.substr(i, n - i));
	}

	return vec;
}

bool check_int(string str)
{
	if (all_of(str.cbegin(), str.cend(), [](char ch) { return isdigit(ch);}))
	{
		return true;
	}
	return false;
}

struct rest {
	string s;
	int p;
	int num;

	/* -------------------------------------
	sort関数を使用したときのソートの定義をする。
	まずは文字列sでソートする。
	文字列sが同じだった場合、pでソートする。
	この条件を参考演算子で表現(ifでもOK)
	-------------------------------------*/
	bool operator<(const rest& right) const {
		return s == right.s ? p > right.p : s < right.s;
	}
};

ll pow_mod(ll n, ll k, ll p) { // n^k(mod p)
	if (k == 0) {
		return 1;
	}
	ll res = pow_mod(n * n % p, k / 2, p);
	if (k & 1) {
		res = res * n % p;
	}
	return res;
}

bool vector_finder(std::vector<int> vec, int number) { // vector 内にnumberがあるかどうか
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return true;
  }
  else { // 発見できなかったとき
    return false;
  }
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> d(k);
	for (int i = 0; i < k; i++) {
		cin >> d[i];
	}

	for (int i = n; ;i++) {
		int j = i;
		bool check = true;
		while(j) {
			int dint = j%10;
			if (vector_finder(d, dint)) {
				check = false;
				break;
			}
			j /= 10;
		}
		if (check) {
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3588
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def divisor(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret

def MI(): return map(int, input().split())


def main():
    N = int(input())
    BTC = 380000.0
    ans = 0

    for i in range(N):
        x, u = input().split()
        x = float(x)
        if u == 'BTC':
            ans += x * BTC
        else:
            ans += x

    print(ans)


if __name__ == '__main__':
    main()


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

string s;
bool m[1010101];

int main(){
  cin >> s;
  reverse(s.begin(), s.end());
  s += '0';
  int n = s.size();
  
  /* これは446に対応できないのでダメ
  rep(i, n + 1) m[i] = false;
  bool flg = false;
  for(int i = n - 1; i >= 0; i--){
    int num = s.at(i) - '0';
    if(num >= 6){
      flg = true;
      continue;
    }
    if(flg && num == 5){
      m[i] = true;
      continue;
    }
    flg = false;
  }
  rep(i, n) cerr << m[i]; cerr << endl;
  */
  
  //rep(i, n) cerr << s.at(i); cerr << endl;
  
  int sum = 0;
  bool flag = false;
  rep(i, n){
    int num = s.at(i) - '0';
    if(flag){ //桁上がり
      flag = false;
      num++;
      /*例外扱いする必要無し
      if(num == 10){
        flag = true;
        num = 0;
      }*/
    }
    if(num >= 6){
      sum += 10 - num;
      flag = true;
    }else if(num == 5 && s.at(i + 1) - '0' >= 5){
      sum += 10 - num;
      flag = true;
    }else{
      sum += num;
    }
    //cerr << num;
  }
     
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1412
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

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

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n; cin >> n;
	vector<ll> a(n); 
	bool z = false;
	bool odd = false;
	ll s = 0;
	rep(i, n)
	{
		int x; cin >> x;
		if (x == 0)z = true;
		else if (x < 0)odd = (true ^ odd);
		a[i] = abs(x);
		s += a[i];
	}
	sort(all(a));
	if (z || !odd)cout << s << endl;
	else cout << s - a[0] * 2 << endl;
}

Measured memory_bytes: 4048
#include <iostream>
#include <iomanip>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int a, b, t, now = 0, ans = 0;
    cin >> a >> b >> t;
    now = a;
    while (now <= t)
    {
        ans += b;
        now += a;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
ll n;
stack<char>s;
int main() {
	scanf("%lld", &n);
	while (1) {
		n--;
		s.push('a' + n % 26);
		n /= 26;
		if (n <= 0)break;
	}
	while (!s.empty()) {
		printf("%c", s.top());
		s.pop();
	}
	puts("");
	return 0;
}

Measured memory_bytes: 3696
import sys
import math
import bisect
 
def main():
    n, m = map(int, input().split())
    wa = [0] * n
    ac = [0] * n
    penalty = 0
    for _ in range(m):
        p, s = input().split()
        p = int(p) - 1
        if s == 'WA':
            wa[p] += 1
        else:
            if ac[p] == 0:
                ac[p] = 1
                penalty += wa[p]
    print('%d %d' % (sum(ac), penalty))
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 4596
A, B, H, M = map(int, input().split())

import math

t = H * 60 + M

ax = A * math.sin(2 * math.pi * t / 720)
ay = A * math.cos(2 * math.pi * t / 720)

bx = B * math.sin(2 * math.pi * t / 60)
by = B * math.cos(2 * math.pi * t / 60)

#print(ax, ay)
#print(bx, by)

dx = ax - bx
dy = ay - by

print(math.sqrt(dx * dx + dy * dy))


Measured memory_bytes: 9528
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

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

    int n = s.length();
    int m = t.length();

    set<string> ans;

    for (int r = n; r >= m; r--) {
        int l = r - m;

        bool ok = true;

        rep(i, m) if (s[l + i] != '?' and s[l + i] != t[i]) ok = false;

        if (ok) {
            string tmp;
            rep(i, n) tmp += s[i];
            rep(i, m) tmp[l + i] = t[i];
            rep(i, n) if (tmp[i] == '?') tmp[i] = 'a';
            ans.insert(tmp);
        }
    }

    if (ans.empty()) {
        cout << "UNRESTORABLE" << endl;
    } else {
        cout << *(ans.begin()) << endl;
    }

}


Measured memory_bytes: 256
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <functional>
#include <queue>
#include <string>
#include <map>
#include <vector>

using namespace std;

int main() {
  string s, f, l("");
  map<string, int> ws;
  getline(cin, s);
  s.push_back(' ');
  int b = -1;
  for (int i = 0; i < s.length(); i++) {
    if (b == -1 && s[i] != ' ')
      b = i;
    if (b >= 0 && s[i] == ' ') {
      ws[s.substr(b, i-b)]++;
      b = -1;
    }
  }
  int maxc = 0;
  for (map<string, int>::iterator it = ws.begin(); it != ws.end(); ++it) {
    if (it->first.length() > l.length())
      l = it->first;
    if (it->second > maxc) {
      f = it->first;
      maxc = it->second;
    }
  }
  cout << f << ' ' << l << endl;
  return 0;
}

Measured memory_bytes: 0
import math
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

def g(a):
    if a == []:
        return(1)
    else:
        b = sorted(a)
        for i in range(0,len(a)):
            if a[0] == b[i]:
                a.pop(0)
                return(i * math.factorial(len(a)) + g(a))

print(abs(g(P)-g(Q)))

Measured memory_bytes: 3064
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int res{0};
    for (size_t i = 0; i < s.size() - 2; ++i) {
        if (s.substr(i, 3) == "ABC") {
            res++;
        }
    }

    cout << res << "\n";
}

Measured memory_bytes: 3576
#include <iostream>
#include <bits/stdc++.h>
#define MAX_SIZE 500010
#define INFTY 2000000000
using namespace std;

struct Node {
    int key;
    Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k) {
    Node *z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    Node *y = NIL;
    Node *x = root;
    while (x != NIL) {
        y = x;
        if (z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == NIL) root = z;
    else if (z->key < y->key) y->left = z;
    else y->right = z;
}

Node *find(int k) {
    Node *x = root;
    while (x != NIL && k != x->key) {
        if (k < x->key) x = x->left;
        else x = x->right;
    }
    return x;
}

void replace(Node *x, Node *y, Node *z) {

}

Node *getMInimum(Node *x) {
    while (x->left != NIL) x = x->left;
    return x;
}

Node *getSuccessor(Node *x) {
    if (x->right != NIL) return getMInimum(x->right);
    Node *y = x->parent;
    while (y != NIL && x == y->right) {
        x = y;
        y = x->parent;
    }
    return y;
}

void deleteNode(Node *z) {
    Node *x, *y;
    if (z->left != NIL && z->right != NIL) y = getSuccessor(z);
    else y = z;
    if (y->left != NIL) x  = y->left;
    else x = y->right;

    if (x != NIL) x->parent = y->parent;

    if (y->parent == NIL) root = x;
    else if (y->parent->left == y) y->parent->left = x;
    else y->parent->right = x;
    if (y != z) z->key = y->key;
    free(y);
}



void findPrint(int k) {
    if (find(k) == NIL) printf("no\n");
    else printf("yes\n");
}

void preorder(Node* u) {
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

void inorder(Node* u) {
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);    
}

void postorder(Node* u) {
    if (u == NIL) return;
    postorder(u->left);
    postorder(u->right);
    printf(" %d", u->key);
}

void print() {
    inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
}

int main(){
    int n, k;
    char cmd[10];
    root = NIL;
    cin >> n;
    for (int i=0; i < n; i++) {
        scanf("%s%d\n", cmd, &k);
        // cout << cmd << k << endl;
        if (cmd[0] == 'i') insert(k);
        else if (cmd[0] == 'f') findPrint(k);
        else if (cmd[0] == 'd') deleteNode(find(k));
        else if (cmd[0] == 'p') print();
    }
    return 0;
} 


Measured memory_bytes: 21864
#String Transformation
import string

def solve():
    s = input()
    t = input()

    dict_s = dict()
    dict_t = dict()
    for c in string.ascii_lowercase:
        dict_s[c] = []
        dict_t[c] = []

    for i, _s in enumerate(s):
        dict_s[_s].append(i)
    for i, _t in enumerate(t):
        dict_t[_t].append(i)
    
    is_ans = True
    for _dict_s in dict_s.values():
        if _dict_s not in dict_t.values():
            is_ans = False
            break

    if is_ans:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

Measured memory_bytes: 21168
n = gets.to_i
a = gets.split.map(&:to_i)

exgcd = ->(x, y){x * y == 0 ? x + y : x.gcd(y)}

l = Array.new(n+1, 0)
n.times {|i| l[i+1] = exgcd.(l[i], a[i])}

r = Array.new(n+1, 0)
n.downto(1) {|i| r[i-1] = exgcd.(r[i], a[i-1])}

ans = 0
n.times do |i|
    x = exgcd.(l[i], r[i+1])
    ans = x if ans < x
end

p ans

Measured memory_bytes: 10124
import java.util.*;
import java.io.*;

/*
   AtCoder contest
   coder : yoichidon
 */
public class Main {

    public  static long[] reverse(long[] array){
        int N = array.length;
        long[] ans = new long[N];
        for(int n=0; n<N; n++) ans[n]=array[N-n-1];
        return ans;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        long[] A = new long[L];
        for(int l=0; l<L; l++) A[l]=sc.nextLong();
        long[] B = reverse(A);


        long[] sum = new long[L+1];
        long[] loopL = new long[L+1];
        long[] endL = new long[L+1];
        long[] loopR = new long[L+1];
        long[] endR = new long[L+1];

        sum[0]=0;
        for(int l=1; l<=L; l++) sum[l] = sum[l-1]+A[l-1];

        loopL[0]=0;
        for(int l=1; l<=L; l++){
            long a = A[l-1];
            if(a==0) loopL[l] = Math.min(sum[l-1], 2+loopL[l-1]);
            else loopL[l] = loopL[l-1] + a%2;
        }

        endL[0]=0;
        for(int l=1; l<=L; l++){
            long a = A[l-1];
            if(a==0) endL[l] = Math.min(sum[l-1], 1+endL[l-1]);
            else if(a%2>0) endL[l] = endL[l-1];
            else endL[l] = Math.min(1+endL[l-1], loopL[l]);
        }

        sum[0]=0;
        for(int l=1; l<=L; l++) sum[l] = sum[l-1]+B[l-1];

        loopR[0]=0;
        for(int l=1; l<=L; l++){
            long b = B[l-1];
            if(b==0) loopR[l] = Math.min(sum[l-1], 2+loopR[l-1]);
            else loopR[l] = loopR[l-1] + b%2;
        }

        endR[0]=0;
        for(int l=1; l<=L; l++){
            long b = B[l-1];
            if(b==0) endR[l] = Math.min(sum[l-1], 1 + endR[l-1]);
            else if(b%2>0) endR[l] = endR[l-1];
            else endR[l] = Math.min(1+endR[l-1], loopR[l]);
        }

        long ans = Long.MAX_VALUE;
        for(int l=0; l<=L; l++) ans = Math.min(ans, endL[l]+endR[L-l]);
        System.out.println(ans);


    }
}


Measured memory_bytes: 95944
/*suri_kumkaran*/
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
typedef long long int int64;
typedef vector<int64> VI64;
typedef vector<pair<int64,int64>> VII64;
typedef vector<string> VS;
typedef vector<vector<int64>> VVI;
 
int64 fast_pow(int64 a,int64 b)
{
  if(b==1)
    return a%MOD;
  int64 sm=fast_pow(a,b/2);
  int64 ans= (sm*sm)%MOD;
  if(b&1)
    ans=(ans*a)%MOD;
  return ans;
}

int64 MI(int64 a)
{
  return fast_pow(a,MOD-2);
}

int main()
{
    IOS;
    int64 T=1,i,j;
    //cin>>T;
    int64 spf[1000005]={0};
    spf[0]=0;
    spf[1]=1;
    for(i=2;i<=1000002;i++)
    {
      if(!spf[i])
      {
        for(j=i;j<=1000002;j+=i)
        {
          if(!spf[j])
            spf[j]=i;
        }
      }
    }
    while(T--)
    {
      unordered_map<int64,int64> lcm;
      int64 n,tem;
      cin>>n;
      int64 ans=0;
      for(i=0;i<n;i++)
      {
        cin>>tem;
        ans+=MI(tem);
        ans%=MOD;
        while(spf[tem]!=1)
        {
          int64 fac=spf[tem];
          int64 cnt=0;
          while(tem%fac==0)
          {
            tem/=fac;
            cnt++;
          }
          lcm[fac]=max(lcm[fac],cnt);
        }
      }
      int64 lcmval=1;
      for(auto x: lcm)
      {
        tem=fast_pow(x.F,x.S);
        lcmval*=tem;
        lcmval%=MOD;
      }
      cout<<(lcmval*ans)%MOD<<endl;
    }
 
    return 0;
}


Measured memory_bytes: 8448
#include <iostream>
#include <bits/c++io.h>
#include <vector>
#include <tuple>
#include <queue>
#define N 100
#define INF 1e9 + 5
using namespace std;

#include <iostream>
#include <bits/c++io.h>
#include <vector>
#include <tuple>
#include <queue>
#define N 100
#define INF 1e9 + 5
using namespace std;

int solve(int n, int k, vector<int> &c, vector<int> &dp)
{
    if (n == 1)
        return 0;
    if (n < 1)
        return INF;
    if (dp[n] != -1)
        return dp[n];
    int best = INF;
    for(int i=1;i<=k;i++){
        if(n-i>0)best = min(best, solve(n-i,k,c,dp)+abs(c[n]-c[n-i]));
    }
    dp[n] = best;
    return dp[n];
}

int main()
{
    int n;
    scanf("%d", &n);
    int k;
    scanf("%d", &k);
    vector<int> c(n + 1);
    vector<int> dp(n + 1, -1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);
    }
    //재귀로 풀어봅시다.
    //solve 는 n일 때 최소가 되는 값을 반환하는 함수라고 합시다.
    dp[0] = INF;
    printf("%d", solve(n, k, c, dp));
    //선형으로 풀어봅시다.
    // dp[0]=0;
    // for(int i =0;i<n;i++){
    //     for(auto j:{i+1,i+2}){
    //         dp[j] = min( dp[j], dp[i]+abs(v[j]-v[i]) );
    //     }
    // }
    // cout<<dp[n-1];

    return 0;
}


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    bool win = true;
    while (a > 0 && c > 0) {
        c -= b;
        if (c <= 0) {
            win = true;
            break;
        }
        a -= d;
        if (a <= 0) {
            win = false;
            break;
        }
    }
    cout << (win ? "Yes" : "No") << endl;

    return 0;
}

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

const int MAXN = 128;

int rec[MAXN][MAXN];

struct Edge {
  int src, dest, weight;
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
Graph g;
vector<int> trace;

inline bool operator< (const Edge &a, const Edge &b) {
  if(a.weight < b.weight) return true;
  if(a.weight > b.weight) return false;
  if(a.src < b.src) return true;
  if(a.src > b.src) return false;
  return a.dest < b.dest;
}
inline bool operator> (const Edge &a, const Edge &b) {
  return b < a;
}

void shortest(int start) {
  int n = g.size();
  trace.assign(n, -2);

  priority_queue<Edge, vector<Edge>, greater<Edge> > q;
  q.push((Edge){-1, start, 0});

  while(!q.empty()) {
        Edge e = q.top();
        q.pop();
        if(trace[e.dest] >= 0) {
          if(trace[e.dest] < e.weight) continue;
        }
        trace[e.dest] = e.weight;
        int a = min(e.src, e.dest);
        int b = max(e.src, e.dest);
        if(a >= 0 && b >= 0) rec[a][b] = rec[b][a] = 2;
        
        for(vector<Edge>::iterator it = g[e.dest].begin(); it != g[e.dest].end(); ++it) {
          int nw = e.weight + it->weight;
          if(trace[it->dest] == -2) {
                q.push((Edge) {it->src, it->dest, e.weight + it->weight});
          } else {
                if(trace[it->dest] == nw) {
                  q.push((Edge) {it->src, it->dest, e.weight + it->weight});
                }
          }
        }
  }
}


int main() {
  int N, M;
  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) rec[i][j] = 0;
  g = vector<Edges>(N);
  for(int i = 0; i < M; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        g[a].push_back((Edge){a, b, c});
        g[b].push_back((Edge){b, a, c});
        rec[a][b] = rec[b][a] = 1;
  }
  vector<int> cnt(3,0);
  for(int s = 0; s < N; s++) {shortest(s);
        //cout << s << " ...." << endl;
  }
  for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
          //cout << i+1 << " " << j+1 << " " << rec[i][j] << endl;
          cnt[rec[i][j]]++;
        }
  }
  //  cout << cnt[0]<< endl;
  cout << cnt[1] << endl;
  //  cout << cnt[2] << endl;
  return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)      x.begin(), x.end()
#define SIZE(x)     static_cast<i64>(x.size())
#define rep(i,n)    for (i64 i = 0, i ## _limit = (n); i < i ## _limit; ++i)
#define reps(i,s,t) for (i64 i = (s), i ## _limit = (t); i <= i ## _limit; ++i)
#define repr(i,s,t) for (i64 i = (s), i ## _limit = (t); i >= i ## _limit; --i)

#ifdef DBG
#define trace(...) _trace(#__VA_ARGS__, __VA_ARGS__);
#else
#define trace(...)
#endif

using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template<class T, class U>inline bool chmax(T &a, const U &b){return b>a && (a=b, true);}
template<class T, class U>inline bool chmin(T &a, const U &b){return b<a && (a=b, true);}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
ostream& operator<< (ostream &os, const vector<T> &vec) {
    rep(i, vec.size()) os << vec[i] << (i+1 == vec.size() ? "" : " ");
    return os;
}

template<class T, class U>
ostream& operator<< (ostream &os, const pair<T, U> &p) {
    return os << p.first << ' ' << p.second;
}

template<class Itr>
ostream& printContainer(Itr begin, Itr end, const string &separator = " ", ostream &os = cout) {
    const auto rbegin = std::prev(end);
    for (; begin != rbegin; ++begin) os << *begin << separator;
    os << *rbegin;
    return os;
}

ostream& operator<< (ostream &os, ostream&) {
    return os;
}

template <class T>
void _trace(const char *s, T&& x) {
    clog << '{';
    while(*s != '\0') clog << *(s++);
    clog << ":" << setw(3) << x << '}' << endl;
}

template <class Head, class... Tail>
void _trace(const char *s, Head&& head, Tail&&... tail) {
    clog << '{';
    while(*s != ',') clog << *(s++);
    clog << ":" << setw(3) << head << "}, ";
    for (++s; !isgraph(*s); ++s);
    _trace(s, std::forward<Tail>(tail)...);
}
// }}} End Header

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

    int N, T;
    i64 a[100010];

    cin >> N >> T;
    rep(i, N) {
        cin >> a[i];
    }

    i64 minv = a[0];
    i64 maxDiff = 0;

    rep(i, N) {
        chmin(minv, a[i]);
        chmax(maxDiff, a[i] - minv);
    }

    int ans = 0;
    minv = a[0];

    rep(i, N) {
        chmin(minv, a[i]);
        if (a[i] - minv == maxDiff) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
import bisect


N = int(input())
L = sorted(map(int, input().split()))
cnt = 0

for i in range(N - 2):
    c = L[i]
    
    for j in range(i + 1, N - 1):
        b = L[j]
        idx = bisect.bisect_left(L, c+b)
        cnt += idx - j - 1
        
print(cnt)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

int main() {
  int N, tmp1 = 0, tmp2 = 0;
  cin >> N;
  vector<int> a(N);
  REP(i, N) {
    cin >> a[i];
  }
  bool c1 = false;
  bool c2 = false;
  bool c3 = false;
  bool c4 = false;
  bool c5 = false;
  bool c6 = false;
  bool c7 = false;
  bool c8 = false;
  REP(i, N) {
    if (a[i] < 400) {
      if (c1 == false) {
        c1 = true;
        tmp1++;
      }
    } else if (a[i] < 800) {
      if (c2 == false) {
        c2 = true;
        tmp1++;
      }
    } else if (a[i] < 1200) {
      if (c3 == false) {
        c3 = true;
        tmp1++;
      }
    } else if (a[i] < 1600) {
      if (c4 == false) {
        c4 = true;
        tmp1++;
      }
    } else if (a[i] < 2000) {
      if (c5 == false) {
        c5 = true;
        tmp1++;
      }
    } else if (a[i] < 2400) {
      if (c6 == false) {
        c6 = true;
        tmp1++;
      }
    } else if (a[i] < 2800) {
      if (c7 == false) {
        c7 = true;
        tmp1++;
      }
    } else if (a[i] < 3200) {
      if (c8 == false) {
        c8 = true;
        tmp1++;
      }
    } else {
      tmp2++;
    }
  }
  if (tmp1 == 0) {
    cout << "1 " << tmp2 << endl;
  } else {
    cout << tmp1 << " " << tmp1 + tmp2 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define N 4
using namespace std;
int main(){
	double x[N], y[N];
	char c;
	while(cin >> x[0] >> c >> y[0]){
		for(int i = 1; i < N; i++){
			cin >> c >> x[i] >> c >> y[i];
		}
		double r[N][2], z[4];
		for(int i = 0; i < N; i++){
			r[i][0] = x[(i+1)%N] - x[i];
			r[i][1] = y[(i+1)%N] - y[i];
		}
		for(int i = 0; i < N; i++){
			z[i] = r[i][0]*r[(i+1)%N][1]-r[(i+1)%N][0]*r[i][1];
		}
		if(z[0]*z[1]*z[2]*z[3] > 0) cout << "YES" << endl;	//??°???????¬????????????????????????°NO
		else cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
N = int(input())

S = [[int(i) for i in input().split()] for i in range(N)] 
S.sort(key=lambda x : (x[1]))

sum = 0
for i in range(N):
    sum += S[i][0]
    if sum > S[i][1]:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 41180