akhauriyash/Code-Regression huggingface dataset:
// ALDS1_9_B.cpp
// Heaps - Maximum Heap

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int left(int i) {
    return 2 * i;
}
int right(int i) {
    return 2 * i + 1;
}

void maxHeapify(vector<int>& A, int i)
{
    int l = left(i);
    int r = right(i);
    int H = A.size();
    int largest = i;
    if (l <= H && A[l] > A[i]) {
        largest = l;
    }
    if (r <= H && A[r] > A[largest]) {
        largest = r;
    }

    if (largest != i) {
        swap(A[i], A[largest]);
        maxHeapify(A, largest);
    }

}

void buildMaxHeap(vector<int>& A)
{
    for (int i = A.size() / 2; i > 0; i--) {
        maxHeapify(A, i);
    }
}

void print(vector<int>& nums) {
    for (int i = 1; i< nums.size(); i++) {
        cout << " " << nums[i];
    }
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    vector<int> heaps(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> heaps[i];
    }
    buildMaxHeap(heaps);
    print(heaps);
    return 0;
}

Measured memory_bytes: 4528
#include <stdio.h>
int main() {
    char str[200];
    char x;
    int i;
    scanf("%[^\n\r]", str);
    for (i = 0; str[i - 1] != ' '; i++) {
    }
    x = str[i];
    printf("A%cC\n", x);
    return 0;
}

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

using namespace std;

typedef long long ll;

#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define inn(x, y) int x,y;cin>>x>>y
#define innn(x, y, z) int x,y,z;cin>>x>>y>>z
#define bit(n) (1<<(n))

#define out(x) cout<<(x)<<endl;
#define outt(x,y) cout<<(x)<<" "<<(y)<<endl;
#define err(x) cerr<<(x)<<endl;
#define errr(x,y) cerr<<(x)<<" "<<(y)<<endl;
#define errrr(x,y,z) cerr<<(x)<<" "<<(y)<<" "<<(z)<<endl;

#define rep(i,n) for (int i=0;i<(n);i++)
#define repp(i,n) for (int i=1;i<=(n);i++)
#define reppp(j, i, n) for (int j=i+1; j<n; j++)

#define lim5 200020
#define lim9 1000000002

#define deg(rad) (((rad)/2/M_PI)*360)
#define mid(min, max) ((min + max) / 2)

int main() {
	in(x);

	out(x / 500 * 1000 + x % 500 / 5 * 5);

	return 0;
}


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

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define piii    pair<int, pair<int, int>>

static const int MOD = 1000000007;

long long extgcd(long long a, long long b, long long& x, long long& y) {
        long long d = a;
        if (b != 0) {
                d = extgcd(b, a % b, y, x);
                y -= (a / b) * x;
        } else {
                x = 1;
                y = 0;
        }
        return d;
}

long long inv(long long a) {
        long long x, y;
        extgcd(a, MOD, x, y);
        return (x % MOD + MOD) % MOD;
}

//long long nHr(long long n, long long r) {
//        return nCr(n + r - 1, r);
//}

long long fact[201010];
 
long long nCr(long long n, long long r){
        long long ans = fact[n] * inv(fact[r]) % MOD * inv(fact[n - r]) % MOD;
        return ans;
}

void init() {
        fact[0] = 1;
        for (int i = 1; i < 201010; i ++) fact[i] = fact[i - 1] * i % MOD;
}

int main() {
        init();
        long long h, w, a, b;
        cin >> h >> w >> a >> b;
        long long ans = 0;
        for (int i = 0; i < h - a; i ++) {
                long long res = nCr(i + b - 1, i);
                res = res * nCr(h - i - 1 + w - b - 1, h - i - 1) % MOD;
                ans = ans + res % MOD;
        }
        cout << ans % MOD << endl;
        return 0;
}



Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
            int N=sc.nextInt();
            int X[] =new int[N];
            int total=0;
            for(int i=0;i<N;i++){
                X[i]=sc.nextInt();
                total+=X[i];
            }
            long C = Math.round((double)total/N);
            int ans=0;
            
            for(int j=0;j<N;j++){
                ans += Math.pow(X[j]-C, 2);
            }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 36200
#include <bits/stdc++.h>
#define ll long long
#define INF LLONG_MAX 
#define dd double 
#define fi first
#define se second
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define dll deque<long long>
#define qll queue<long long>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define vvll vector<vector<ll>>
#define vpll vector<pair<long long,long long>>
#define vpcl vector<pair<char,long long>>
#define vpsl vector<pair<string,long long>>
#define stll stack<long long>
#define stc stack<char>
#define mll map<long long,long long>
#define pll pair<long long,long long>
#define psl pair<string,long long>
#define mcl map<char,long long>
#define msl map<string,long long>
#define pcl pair<char,long long>
#define mmll multimap<long long,long long> 
#define mmcl multimap<char,long long>
#define mmsl multimap<string,long long>
#define sll set<long long>
#define sc  set<char>
#define ss  set<string>
#define msll multiset<long long>
#define msc  multiset<char>
#define mss  multiset<string>
#define lb lower_bound
#define up upper_bound
#define lt length
#define clr clear
#define ap append
#define sz size
#define sub substr
#define ull unsigned long long int
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
//#include <boost/multiprecision/cpp_int.hpp> 
//using boost::multiprecision::cpp_int; 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

ll modexp(ll x,ll n,ll p){    //modular exponential function
  if(n==0){return 1;}
  ll u = modexp(x,n/2,p);
  u = u*u%p;
  if(n%2==1){u=(u*x)%p;}
  return u;
}

ll gcd (ll a, ll b) {     //Eulers algorithm
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}

ll m = 1e9+7;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll h,w; cin>>h>>w;
    string arr[h];
    ll dp[h][w];
    rep(i,0,h-1){
        rep(j,0,w-1){
            dp[i][j]=-1;
        }
    }
    dp[0][0]=1;
    rep(i,0,h-1){
        cin>>arr[i]; 
    }
    rep(i,0,h-1){
        rep(j,0,w-1){
            if(arr[i][j]=='#'){dp[i][j]=0;}
        }
    }
    rep(i,0,h-1){
        rep(j,0,w-1){
            if(i==0 && j==0){dp[i][j]=1; continue;}
            if(i==0){
                if(dp[i][j]!=0){
                    dp[i][j] = dp[i][j-1]%m;
                }
                continue;
            }
            if(j==0){
                if(dp[i][j]!=0){
                    dp[i][j] = dp[i-1][j]%m;
                }
                continue;
            }
            if(dp[i][j]!=0){
                dp[i][j] = (dp[i-1][j]%m + dp[i][j-1]%m)%m;
        }
        }
    }
    cout<<dp[h-1][w-1];
}


Measured memory_bytes: 12376
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x) cout<<#x<<" = "<<(x)<<endl;
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  int a,b; cin >> a >> b;
  COUT(b%a ? b-a : a+b);
  return 0;
}

Measured memory_bytes: 256
INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = min(i + a, H)
        dp[idx] = min(dp[idx], dp[i] + b)

print(dp[H])

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

int board[3][3];

int main(){
  rep(i,3) rep(j,3) cin >> board[i][j];
  int n; cin >> n;
  rep(i,n){
    int x; cin >> x;
    rep(j,3) rep(k,3){
      if(board[j][k] == x) board[j][k] = 1;
    }
  }

  bool bingo = false;
  rep(i,3) {
    int cnt = 0;
    rep(j,3){
      cnt += board[i][j];
    }
    if(cnt == 3) bingo = true;
  }

  rep(i,3){
    int cnt = 0;
    rep(j,3){
      cnt += board[j][i];
    }
    if(cnt == 3) bingo = true;

    cnt = 0;
    rep(j,3){
      cnt += board[j][j];
    }
    if(cnt == 3) bingo = true;

    cnt = 0;
    rep(j,3){
      cnt += board[j][2-j];
    }
    if(cnt == 3) bingo = true;
  }

  puts(bingo?"Yes":"No");


  return 0;
}

Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N; cin >> N;
    vi h(N); REP(i, N) cin >> h[i];

    int vtx = 0;
    REP(i, N) vtx += h[i];

    int eg = 0;
    FOR(i, 1, N) eg += min(h[i - 1], h[i]);

    int ans = vtx - eg;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD=1e9+7;
const int INF=1<<29;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" ";}
inline int powerexp(int a,int b,int m=MOD){int res=1;while(b){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res%m;}
inline int modinv(int a){return powerexp(a,MOD-2,MOD);}
inline int lcm(int a,int b){int g=__gcd(a,b);return a/g*b;}

//-------------------< start here >-------------------------// 
void solve(){
     int n;
     cin >> n;
     vector<int> v(n);
     for(auto &it : v) cin >> it;
     int cnt = 0;
     for(int i=1;i+1<n;i++){
		  cnt+=((v[i]>v[i-1] and v[i]<v[i+1])or(v[i]<v[i-1] and v[i]>v[i+1]));
		}
   cout << cnt << endl;    
}
//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
   #endif
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <set>
#include <map>
#include <queue>

#define sz(v) int(v.size())
#define sqr(x) ((x) * (x))

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <class T>
using indexed_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T1, class T2>
istream& operator >> (istream &in, pair <T1, T2> &a) {
    in >> a.first >> a.second;
    return in;
}

template <class T1, class T2>
ostream& operator << (ostream &out, pair <T1, T2> &p) {
    out << p.first << ' ' << p.second;
    return out;
}

template <class T>
istream& operator >> (istream &in, vector <T> &a) {
    for (T &i: a) in >> i;
    return in;
}

template <class T>
ostream& operator << (ostream &out, vector <T> &a) {
    for (T i : a) out << i << ' ';
    return out;
}

void fastIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
}

int n;

int main() {
    fastIO();

    cin >> n;
    set <string> s;
    for (int i = 0; i < n; ++i) {
        string t;
        cin >> t;
        
        s.insert(t);
    }
    
    cout << sz(s);
    
    return 0;
}

/// ЗАПУСКАЕМ ГУСЯ
/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */

Measured memory_bytes: 19276
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fori(i,a,b) for(int i=a;i<=b;i++)

unordered_map<ll,ll> mp;

int main()
{
    ll n;
    cin>>n;
    cout<<n*(n-1)/2<< endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <set>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <numeric>

using namespace std;

typedef long long ll;

#define forn(i, n) for(int i = 0; i < (int)(n);++i)
#define fore(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define fi first
#define se second
#define pb push_back
#define pll pair<ll,ll>
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vi>
#define vpll vector<pll>
#define vll vector<ll>
#define vvll vector<vll>
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()


void fastik() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

//ifstream &cin
void solve(){

}

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

    vll p(n);
    forn(i,n) cin >> p[i];
    ll ans = 0;
    fore(i,1,n-2){
        vll a = {p[i-1],p[i],p[i+1]};
        sort(all(a));
        if(p[i] == a[1]){
            ans++;
        }
    }
    cout << ans;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define            ll              long long
#define            pb              push_back
#define            mp              make_pair
#define            loop(i,a,n)     for(int i=a;i<n;++i)
#define            clr(x)          memset(x,0,sizeof x)
#define            min3(a,b,c)     min(a,min(b,c))
#define            max3(a,b,c)     max(a,max(b,c))
#define            min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define            max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define            fast            ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define            pii             pair<int,int>
#define            pll             pair<ll,ll>
#define            pli             pair<ll,int>
#define            pil             pair<int,ll>
#define            FF              first
#define            SS              second
#define            PI              acos(-1.0)
#define            bug             cout<<"ok"<<endl;

using namespace std;
using namespace __gnu_pbds;

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

const int MOD = 1e9 + 7;
const ll MX= 1e9;
const ll INF = 1e9;


ll dp[100009];


main()
{
   int n,k;
   cin>>n>>k;
   int a[n+9];
   loop(i,0,n)cin>>a[i];
   dp[0]=0;
   dp[1]=abs(a[0]-a[1]);
   loop(i,2,n)
   {
       dp[i]=INF;
       loop(j,1,k+1)
       if(i-j>=0)dp[i]=min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
       //cout<<i<<"->"<<dp[i]<<endl;

   }
   cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1408
import collections

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A,B=map(int, input().split())
N=gcd(A,B)
c = collections.Counter(prime_factorize(N))
print(len(list(c.keys()))+1)

Measured memory_bytes: 3316
/**
 * Я слил Atcoder Beginner Contest 172, решив всего две задачи!
 * Я не могу апнуть синего!
 * Я постоянно сливаю раунды, либо не решив тупую задачу, либо набрав штрафа!
 * Я постоянно уступаю всем своим друзьям и знакомым в контестах и нахожу этому оправдания!
 * Я постоянно придумываю сложные неверные решения к простым задачам!
 * -------------------------------------------------------------
 * -Решать сложные задачи
 * -Участвовать в контестах
 * -Делать виртуальные соревнования
 * -------------------------------------------------------------
 * Не уберу это, пока не начну нормально решать задачи, а не заниматься ерундой!!!
**/
  
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
typedef long long  ll;
//typedef tree<ld,null_type,less<ld>,rb_tree_tag,tree_order_statistics_node_update> indexed_set
// this for long double
#define press_F_to_pay_respect ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn for(int i=0;i<n;i++) 
#define form for(int j=0;j<n;j++) 
#define fore(i,a,b) for(int i = a; i < (b); i++)
#define pb push_back 
#define pob pop_back()
#define mp make_pair 
#define sc second 
#define f first 
#define ld long double
#define kek cout<<endl; 
#define rep(i,a,b) for(int i=a;i<b;i++)
#define all(v) ((v).begin()), ((v).end()) 
#define pob pop_back() 
#define halt {cout<<"NO"; return 0;}
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const int N = 1010;
const int INF = 1e8;
const ll LL_INF=1e10;
const ll MOD1=1073741824;
const long double pi=3.1415926535;
using namespace std;
using namespace __gnu_pbds;
typedef tree<ld,null_type,less<ld>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
string bin_rep(int n)
{
     string s="";
      for(int i=31;i>=0;i--)
   {
           if(n&(1<<i)) s+='1';
           else s+='0';
   }
   return s;
}
int main()
{
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
 press_F_to_pay_respect;
 // cout << fixed << setprecision(12) << ans;
 // string al = "abcdefghijklmnopqrstuvwxyz";
 int n;
 cin>>n;
 n%=1000;
 if(!n) cout<<0;
 else cout<<1000-n;
 
 
 
 
 
 
 
 
 
  // cout <<"Runtime is:"<<clock() * 1.0 / CLOCKS_PER_SEC <<endl;
   return 0;
   
   
 
}

Measured memory_bytes: 3648
import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int h = sc.nextInt();
        int m = sc.nextInt();

        double ax = a * Math.sin(Math.PI * 2 * (1d / 12 * h + 1d/12/60 * m));
        double ay = a * Math.cos(Math.PI * 2 * (1d / 12 * h + 1d/12/60 * m));
        double bx = b * Math.sin(Math.PI * 2 / 60 * m);
        double by = b * Math.cos(Math.PI * 2 / 60 * m);

        System.out.printf("%.20f\n", Math.hypot(bx-ax, by-ay));
    }
}

Measured memory_bytes: 36152
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<set>
#include<math.h>

using namespace std;

int main(void)
{
    int n,m;
    cin>>n>>m;
    
    int l[m],r[m];
    
    for(int i=0;i<m;i++){
        cin>>l[i]>>r[i];
    }
    
    int a=l[0],b=r[0];
    int break_flag=0;
    
    for(int i=1;i<m;i++){
        if(r[i]<a || l[i]>b){
            break_flag=1;
            break;
        }
        else if(l[i]>=a && r[i]<=b){
            a=l[i];b=r[i];
        }
        else if(r[i]<=b){
            b=r[i];
        }
        else if(l[i]>=a){
            a=l[i];
        }
    }
    
    if(break_flag==1){
        cout<<0<<endl;
    }
    else{
        cout<<b-a+1<<endl;
    }
    
    
    
    
}


Measured memory_bytes: 1024
import sys

s = sys.stdin.readline().rstrip()
x, y = map(int, sys.stdin.readline().split())

def reachable(deltas, goal):
    if not deltas:
        if goal == 0:
            return True
        else:
            return False
    
    s = sum(deltas)
    if goal < -s or s < goal:
        return False

    res = [False] * (s * 2 + 1) 
    res[s] = True
    
    for d in deltas:
        prev = res.copy()
        res = [False] * (s * 2 + 1)
        for i in range(s*2+1):
            if prev[i]:
                res[i+d] = res[i-d] = True

    return res[s + goal]


def main():
    gx = x; gy = y
    dx = []
    dy = []
    direction = 0

    origin_x = 0
    for i in s:
        if i == 'T':
            break
        origin_x += 1
    gx -= origin_x

    tmp = 0
    for i in s[origin_x:] + 'T':
        if i == 'T':
            if direction == 0:
                if tmp != 0:
                    dx.append(tmp)
                direction = 1
            else:
                if tmp != 0:
                    dy.append(tmp)
                direction = 0
            tmp = 0
        else:
            tmp += 1

    return 'Yes' if reachable(dx, gx) & reachable(dy, gy) else 'No'
    
if __name__ == '__main__':
    ans = main()
    print(ans)

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

int main() {
  double  W, H, x, y, menseki_d;
  
  cin >> W >> H >> x >> y;

  menseki_d = W * H / 2.0;
  
  int saiteki = 0;
    
  if(x == W/2 && y == H / 2){
   saiteki = 1;
  }

  cout << menseki_d << ' ' << saiteki << endl;

}

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

long pow(long long x,long long n) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return (pow(x % M * x % M, n/2)% M);
  else if (n % 2 != 0)
    return (pow(x % M * x % M,n/2) % M * x % M);
}

int main() {
  long long m,n;
  cin >> m >> n;
  cout << pow(m,n) % M << endl;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 10000000;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> path(N);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    
    vector<pair<int, int>> guides(N);
    for (int i = 0; i < N; i++)
        guides[i] = make_pair(-1, INF);
    queue<vector<int>> que;
    vector<int> first_push = {-1, 0, 0};
    que.push(first_push);
    while(!que.empty()) {
        int before_node_no = que.front()[0];
        int node_no = que.front()[1];
        int path_length = que.front()[2];
        que.pop();
        
        if (guides[node_no].second > path_length) {
            guides[node_no] = make_pair(before_node_no, path_length);
            for (int i = 0; i < path[node_no].size(); i++) {
                if (guides[path[node_no][i]].second > path_length+1) {
                    vector<int> p = {node_no, path[node_no][i], path_length+1};
                    que.push(p);
                }
            }
        }
    }
    
    cout << "Yes" << endl;
    for (int i = 1; i < N; i++)
        cout << guides[i].first+1 << endl;
}

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

int main() {
    ll n;
    std::cin >> n;
    vector<bool> seats(20);

    string first;
    string last;
    
    ll l,r;
    l = 0;
    r = n-1;
    
    std::cout << 0 << std::endl;
    std::cin >> first;
    if(first == "Vacant")return 0;
    std::cout << n-1 << std::endl;
    std::cin >> last;
    if(last == "Vacant")return 0;
    ll rem =18;
    while(rem>0){
        ll pos = (l+r)/2;
        string tmp;
        std::cout << pos << std::endl;
        std::cin >> tmp;
        
        if(tmp == "Vacant")return 0;
        
        if( (tmp == last) ^ ((r-pos)%2==0)){
            l = pos;
            first = tmp;
        }else{
            r = pos;
            last = tmp;
        }
        
        
        rem--;
    }
}


Measured memory_bytes: 852
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

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 all(x) x.begin(),x.end()


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

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

const int MAXN = 200 ; 
int n , a[MAXN] , ans ; 

int main()
{
	cin >> n ;
	n*=2 ; 
	for(int i=0 ; i<n ; i++)
		cin >> a[i] ;
	sort(a , a+n) ;  
	for(int i=0 ; i<n ; i+=2)
		ans+=a[i] ; 
	cout << ans << endl ;
}


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

const int mod = 1000000000+7;

ll factorial(ll x){
  ll ret = 1;
  while (x){
    ret *= x;
    ret %= mod;
    x--;
  }
  return ret;
}

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

int main(){
  ll x, y;
  cin >> x >> y;
  ll s = 2*x - y, t = 2*y - x;
  ll ans;
  if (s >= 0 && t >= 0 && !(s%3) && !(t%3)) {
    ll a = s / 3, b = t / 3;
    ans = factorial(a+b);
    ll c =  ll(factorial(a) * factorial(b)) % mod;
    ans *= mod_pow(c, mod - 2);
    ans %= mod;
  } else {
    ans = 0;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/**
 *    author: gxfireball       
**/
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
using namespace std;

void solve(){
   ll n,m;
   cin >> n >> m;
   ll temp,sum=0;
   for(ll i=0; i<m; ++i){
	   cin >> temp;
	   sum += temp;
   }
   if(sum <= n){
	   cout << n - sum << endl;
   }
   else cout << -1 << endl; 
}

int main(){
    fastio;
    int t;
    t = 1;
    //cin>>t;
    while(t--){
    	solve();
    }
    return 0;
}


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

int main(){
	int i, j, n, l, r, ans;

	// input
	scanf("%d\n", &n);

	// calc
	ans = 0;
	for (i = 0; i < n; i++) {
		scanf("%d %d\n", &l, &r);
		ans += r - l + 1;
	}
	
	// output
	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 128
#pragma GCC target (*sse4.2*)
#pragma GCC optimization ("O3")
#pragma GCC optimize ("Ofast")
#define mod 1000000007
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#define PB push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define vvii vector<vii>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define read(x) int x;cin>>x;
#define FOR(a,b,c,d) for(int a=b;a<=c;a+=d)
#define MP make_pair
#define F first
#define S second
#define debug(x) cout<<("#x)<<": "<<(x)<<"\n"
#define SZ(x) x.size()
#define INF 1<<10

using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double d64;

int main(){
fast
char x;cin>>x;
bool d=0;
for(int i='A';i<='Z';i++){
    if(x==i){
        cout<<"A";
        d=1;
        break;
    }
}
if(!d)cout<<"a";
return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d;
  int left, right;
  
  cin >> a >> b >> c >> d;
  
  left = a + b;
  right = c + d;

  if (left > right) {
    cout << "Left" << endl;
  } else if (left < right) {
    cout << "Right" << endl;
  } else {
    cout << "Balanced" << endl;
  }
  
}

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

using namespace std;

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

int X[100100];
int main(){
    int N, M;
    cin >> N >> M;
    REP(i,M){
        int x;
        cin >> x;
        X[i] = x;
    }

    if(M == 1){
        cout << 0 << endl;
        return 0;
    }

    sort(X, X+M);
    ll sum = X[M-1] - X[0];

    vector<ll> diff(M-1);
    //vector<ll> sum(M);
    //sum[0] = X[0];
    for(int i = 0; i < M-1; i++){
        diff[i] = X[i+1] - X[i];
        //sum[i+1] = sum[i] + X[i+1];
    }

    sort(diff.begin(), diff.end(), greater<ll>());
    ll ans = sum;
    for(int i = 0; i < N-1; i++){
        if(i >= M-1) break;
        ans -= diff[i];
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

namespace string_helper
{
	bool check_palindrome(const string& word, int& ret)
	{
		if (word.empty()) return true;

		size_t lo = 0;
		size_t hi = word.size() - 1;

		while (lo < hi)
		{
			if (word[lo] != word[hi])
			{
				ret++;
			}

			lo++;
			hi--;
		}

		return true;
	}
}

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

	string S;
	cin >> S;

	int ret = 0;
	string_helper::check_palindrome(S, ret);

	cout << ret;

	return 0;
}


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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (n - 1); i > (a - 1); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define updiv(a, b) ((a + b - 1) / b)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, 1, -1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

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

  int n;
  cin>>n;
  vector<int> a(n),b(n),c(n);
  rep(i,0,n) cin>>a[i];
  rep(i,0,n) cin>>b[i];
  rep(i,0,n) cin>>c[i];
  sort(all(a)),sort(all(b)),sort(all(c));
  int ans = 0;

  rep(i,0,n){
    int low = lower_bound(all(a),b[i]) - a.begin();
    int hig = c.end() - upper_bound(all(c),b[i]);
    ans += low * hig;
  }
  cout<<ans<<'\n';
  return 0;
}

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

#define int				long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )	for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )	FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP				make_pair
#define X				first.first
#define Y				first.second

typedef pair<int, int> P;

template<class T>bool chmax( T& a, const T& b ) { if( a < b ) { a = b; return 1; } return 0; }
template<class T>bool chmin( T& a, const T& b ) { if( a > b ) { a = b; return 1; } return 0; }

const int INF = 1e9;
const int MOD = 1e9 + 7;

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

char orchard[101][101];
int H, W;

void dfs( int sx, int sy, char f ) {
	REP( i, 4 ) {
		int nx = sx + dx[i];
		int ny = sy + dy[i];

		if( nx >= 0 && nx < W && ny >= 0 && ny < H && orchard[nx][ny] == f ) {
			orchard[nx][ny] = '.';
			dfs( nx, ny, f );
		}
	}
}

signed main() {

	while( cin >> H >> W ) {
		if( H == 0 && W == 0 ) break;

		REP( i, H ) {
			REP( j, W ) {
				cin >> orchard[j][i];
			}
		}

		int ans = 0;
		REP( i, H ) {
			REP( j, W ) {
				if( orchard[j][i] != '.' ) {
					dfs( j, i, orchard[j][i] );
					ans++;
				}
			}
		}

		cout << ans << endl;

	}
}


Measured memory_bytes: 3516
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int a = 1;
        int cnt = 0;
        do {
            a = a * R;
            cnt++;
        } while (a <= N);

        System.out.println(cnt);
    }
}


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

string s;
int n;

int gt(int mask) {
    int res = 0, now = 0;
    for (int i = 0; i < n; ++i) {
        now = now * 10 + s[i] - '0';
        if (mask & (1 << i)) {
            res += now;
            now = 0;
        }
    }
    res += now;
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    n = s.size();
    int ans = 0;
    for (int mask = 0; mask < (1 << (n - 1)); ++mask) {
        ans += gt(mask);
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
  int a, b, c, x, y, money;
  cin >> a >> b >> c >> x >> y;
  if(a + b <= 2*c){
    money = a*x + b*y;
  } else if (x < y){
    if(b <= 2*c) money = 2*c*x + b*(y-x);
    else money = 2*c*y;
  } else {
    if(a <= 2*c) money = 2*c*y + a*(x-y);
    else money = 2*c*x;
  }
  cout << money << endl;
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    A, B = map(int, readline().split())
    s = input()
    nums = "0123456789"

    def judge():
        if s.count("-") == 1:
            if s[A] == "-":
                first, second = s.split("-")
                for c in first:
                    if c not in nums:
                        return False
                for c in second:
                    if c not in nums:
                        return False
                return True
        return False

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


if __name__ == '__main__':
    main()


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

//const ll INF=(ll)1e19;
const int INF=(1<<30);

int M[10] = {0,2,5,5,4,5,6,3,7,6};
 
int main(){
  int n,m;
  cin >> n >> m;

  VI a(m);
  REP(i,m)cin >> a[i];
  sort(a.rbegin(), a.rend());
  // dp[i]: i本で作れる桁数
  vector<int> dp(n+1,-1);
  dp[0]=0;

  REP(i,n){
    REP(j,m){
      if(i+M[a[j]] <= n && dp[i+M[a[j]]] < dp[i]+1){
        dp[i+M[a[j]]] = dp[i]+1;
      }
    }
  }

  // REP(i,n+1){
  //   cout << i << " " << dp[i] << endl;
  // }

  VI ans;
  for(int i=n; i> 0; ){
    REP(j,m){
      if(i-M[a[j]] >= 0 && dp[i] == dp[i-M[a[j]]] + 1){
        ans.emplace_back(a[j]);
        i -= M[a[j]];
        break;
      }
    }
  }
  for(auto v: ans)cout << v;
  cout << endl;
}



Measured memory_bytes: 384
n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  dic[i+1]=a[i]
 
dic2 = sorted(dic.items(), key=lambda x:x[1])
 
ans=""
for i in dic2:
  print(i[0],end=" ")
  
  
  
print(ans)

Measured memory_bytes: 25576
#include<stdio.h>
int main(){
int a[10010],n,i,j,c,d=0;
scanf("%d\n",&n);
for(i=0;i<10001;i++){
a[i]=0;
}
for(i=0;i<n;i++){
scanf("%d",&c);
a[c]++;
}
for(i=0;i<10001;i++){
for(j=0;j<a[i];j++){
if(d==0){
printf("%d",i);
d++;
}
else{
printf(" %d",i);
}
}
}
printf("\n");
return 0;
}


Measured memory_bytes: 2148
#include <iostream>
#include <vector>
#include<algorithm>
#include <string>
#include <cmath>
#include<queue>
#define PI 3.141592653589793238
#define ll long long
using namespace std;

int main()
{
	char n;

	cin >> n;

	cout << (char)(n + 1);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 5e4+10, M = 1e5+10;
int n,m,T;

bitset<N>b[N];
vector<pair<pa,int>>v[N];
int ans[M],l[N];
inline void dfs(int u,int las){
	int L=l[u];
	while (l[u]<siz(v[u])&&v[u][l[u]].fi.se<las) ans[v[u][l[u]].fi.se]=v[u][l[u]].se,++l[u];
	FOR(i,L,l[u]) dfs(v[u][i].fi.fi,v[u][i].fi.se);
}
inline void solve1(){
	For(i,1,n) b[i][i]=1;
	For(i,1,m){
		int x=read(),y=read();
		b[x]=b[y]=b[x]|b[y];
		v[x].ep(mp(y,i),1),v[y].ep(mp(x,i),0);
		ans[i]=-1;
	}
	bool flag=0;
	For(i,1,n) if (b[i].count()==n){
		dfs(i,1e9),flag=1;break;
	}
	if (!flag) puts("-1");
		else For(i,1,m) printf("%c",(ans[i]==1||ans[i]==-1)?'^':'v');
}

int x[M],y[M],siz[N],to[N];
inline void upd(int x,int y){
	siz[to[x]]--,to[x]=y,siz[to[x]]++;
}
inline void solve2(){
	For(i,1,m) x[i]=read(),y[i]=read();
	For(i,1,n) to[i]=i,siz[i]=1;
	Dow(i,m,1){
		if (max(siz[to[x[i]]]-1,siz[to[y[i]]]+1)<max(siz[to[x[i]]]+1,siz[to[y[i]]]-1)){
			ans[i]=0,upd(x[i],to[y[i]]);
		} else {
			ans[i]=1,upd(y[i],to[x[i]]);
		}
	}
	bool flag=0;
	For(i,1,n) if (siz[i]==n) flag=1;
	if (flag) puts("-1");
		else For(i,1,m) printf("%c",ans[i]==1?'^':'v');
}

int main(){
	n=read(),m=read(),T=read();
	if (T==1) solve1();
		else solve2();
}

Measured memory_bytes: 317444
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
int v[10001], w[10001];
int cache[3001][3001];
pair<int, int> p[3001][3001];
int calc(string &s, int S, string &t, int T) {
	if(S==0 || T==0) {
		return 0;
	}
	
	if(cache[S][T]!=-1) {
		return cache[S][T];
	}
	
	int mx = 0;
	if(s[S-1]==t[T-1]) {
		mx = calc(s, S-1, t, T-1) + 1;
	}
	
	int one = calc(s, S-1, t, T);
	int two = calc(s, S, t, T-1);
	
	/*if(two >= mx && two>=one) {
		p[S][T] = make_pair(S, T-1);
	}
	if(one >= mx && one>=two) {
		p[S][T] = make_pair(S-1, T);
	}
	if(mx >= one && mx>=two) {
		p[S][T] = make_pair(S-1, T-1);
	}*/
	return cache[S][T] = max(mx, max(one,two));
}

string print(string s, string t, int l, int r) {
	if(l==0 || r==0) {
		return "";
	}
	
	if(s[l-1]==t[r-1]) {
		return print(s,t,l-1, r-1) + s[l-1];
	}
	
	if(cache[l-1][r] > cache[l][r-1]) {
		return print(s, t, l-1, r);
	}
	
	return print(s, t, l, r-1);
}
int main() {
	string s,t;
	cin>>s>>t;
	for (int i=0; i<=3000; i++) {
		for (int j=0; j<=3000; j++) {
			cache[i][j] = -1;
		}
	}
	int ans = calc(s, s.size(), t, t.size());
	cout << print(s,t, s.size(), t.size());
	
	return 0;
}

Measured memory_bytes: 72704
#include<bits/stdc++.h>
using namespace std;
long long a[101],w[101],v[101],i,j,n,res=0,f[100001],ww,m;
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++) 
	{
		cin>>w[i]>>v[i];
		ww=ww+v[i];
	}
	for(i=1;i<=1e5;i++) f[i]=1e15;
	for(i=1;i<=n;i++)
	for(j=ww-v[i];j>=0;j--)
	{
		f[j+v[i]]=min(f[j+v[i]],f[j]+w[i]);
	}
	for(i=ww;i>=0;i--) if(f[i]<=m)
	{
		cout<<i;
		return 0;
	}
}

Measured memory_bytes: 4416
n = int(input())
a = [int(i) for i in input().split()]

sum = 0
cnt = 0
d = 1000000000
for i in a:
    if (i < 0):
        cnt += 1;
        sum -= i
        if (-i < d):
            d = -i
    elif (i >= 0):
        sum += i
        if (i < d):
            d = i

if (cnt % 2 == 1):
    sum -= 2 * d

print(sum)


Measured memory_bytes: 14412
from heapq import heappush, heappop
n, m = map(int, input().split())
B = [[] for _ in range(m+1)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m: B[a] += [-b]
C = []
s = 0
for i in range(m+1):
    for b in B[i]: heappush(C, b)
    if C: s += heappop(C)
print(-s)

Measured memory_bytes: 66592
/* 
    AABRA KA DABRA.. !! 
*/
#include "bits/stdc++.h"
using namespace std;
typedef long double ld;
typedef pair<int,int> pii;
#define int long long
#define RAGE ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,n) for(i=0; i <n; i++)
#define repv(i,k,n) for(int i=k; i<=n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define endl '\n'
#define deb(x) cout<<#x<<" = "<<x<<endl
#define gcd __gcd
#define inf LLONG_MAX
#define minf LLONG_MIN 
const int mod = (int)(1e9+7);

int power(int x,int n)
{   
    if(n==0)    return 1;
    if(n==1)    return x%mod;
    if(n%2==0)  {   int y = power(x,n/2)%mod;return (y*y)%mod;}
    if(n&1)     {   int y = power(x,n-1);return (x%mod * y%mod)%mod;}
    return 0;
}
bool is_power_2(int n)  { return log2(n)==floor(log2(n));}
bool is_prime(int n){   for(int i=2; i*i<=n; i++)   if(n%i==0)  return 0;   return 1;}

int dx[]    =  { 1 ,  0,  -1,  0,  -1,  -1,  1,   1};
int dy[]    =  { 0 ,  1,  0, -1,  -1,   1,  1,  -1};
char dir[]  =  {'D','R','U','L'};

const int maxn = 200005;

/* ------------------------------------------------------- */



void solve()
{
    int n,i,j,k,m;
    cin>>n;
    int ans = n+ n*n+ n*n*n;
    cout<<ans;
}
signed main()
{
    RAGE;
    
    int t=1;
    //  cin>>t;
    while(t--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (auto& x : A) cin >> x;
	if (N % 2 == 1) {
		long long sum = 0;
		for (auto x : A) sum += x;
		cout << (sum % 2 == 1 ? "First" : "Second") << endl;
		return 0;
	}
	auto m = *min_element(A.begin(), A.end());
	long long s = 0;
	for (auto x : A) s += x - m;
	cout << ((m % 2 == 1 || s % 2 == 1) ? "First" : "Second") << endl;
}



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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;

#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
// #define mp make_pair
//#define endl '\n'

int main() {
  string s, t;
  cin >> s >> t;
  int ans = 0;
  rep (i, 3) {
    ans += s[i] == t[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# N <= 300 O(n ** 3)まで
# 何通り dp or combo
N = getN()
# 1つ目の譜面
B = []
for i in range(N):
    q = list(input())
    B.append(q * 2)
B += B
# 2つ目にはなにも書かれてない
# 2つ目の盤面に縦にi、横にjずらして数字を記入する

# 対角線に対して線対称なものの数を求める
# 整数a, bの選び方が何通りあるか

def judge(a, b):
    """
    res = [[''] * N for i in range(N)]
    # 盤面１のB[i][j]を盤面2に書き込む
    for i in range(N):
        for j in range(N):
            res[(i + a) % N][(j + b) % N] = B[i][j]
    """

    for i in range(N):
        for j in range(N):
            if B[i + a][j + b] != B[j + a][i + b]:
                return 0
        else:
            continue
        break
    else:
        return 1

# 全てのa, bについて調べるなら１つの(a, b)についてO(N)で求める必要がある
# 判定する際、節約出来ないか？

# N * N のゾーンをずらしていく
# a [b  a] b
# c [a  c] a
# a  b  a  b
# c  a  c  a 対称軸がずれる 軸は2N - 1本ある
# 良い盤面になる条件

# 斜めにずらしていくことで前の結果を利用できる
# 1本の軸について判定した時、1つの盤面が良い盤面なら他全ても良い盤面
# 軸に刺さっている盤面の数を求めればいい

# 軸は2N - 1本ある
# 縦に対角線をずらす
ans = 0
for i in range(N):
    # 軸(0, i)にはN - i本の盤面が連なっている
    # 連なっている全ての盤面は全てTrueか全てFalse
    ans += (N - i) * judge(i, 0)

# 横に対角線をずらす
for i in range(1, N):
    ans += (N - i) * judge(0, i)
print(ans)

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> vec(n);
  int a=0,b=0;
  
  for(int i=0; i<m ;i++){
    cin >> a >>b;
    vec.at(a-1) = vec.at(a-1)+1;
    vec.at(b-1) = vec.at(b-1)+1;
  }
  for(int i=0; i<n ; i++){
    cout << vec.at(i) << endl;
  }
}

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

using namespace std;
typedef long long ll;

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

  string a, b, c;
  cin >> a >> b >> c;

  if (a.back() == b.front() && b.back() == c.front()) cout << "YES" << "\n";
  else cout << "NO" << "\n";
}


Measured memory_bytes: 3600