akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

const int MX = 131072;
ll bit[MX], cnt[MX];
inline ll sum(ll *bit, int i){
	ll res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}
inline void add(ll *bit, int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
inline ll sum(int k){
	int lo = 0, hi = MX, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(cnt[mid] >= k) hi = mid;
		else lo = mid, k -= cnt[mid];
	}
	return sum(bit, lo) + hi * k;
}

int main(){
	int n;
	scanf("%d", &n);
	vector<pi> v;
	rep(i, n){
		int a, b;
		scanf("%d%d", &a, &b);
		v.pb(mp(-b, a));
	}
	sort(all(v));
	int ans = 0, k = 0;
	
	rep(i, n){
		int b = -v[i].first, a = v[i].second;
		bool flag = 0;
		add(bit, a, a);
		add(cnt, a, 1);
		
		while(k <= i && sum(k + 1) <= (ll)b * (k + 1)) k++, flag = 1;
		if(!flag) while(k > 0 && sum(k) > (ll)b * k) k--;
		ans = max(ans, k);
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 7228
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

signed main() {
    int n;
    while (cin >> n) {
	if (!n) break;

	vector<int> x, y;
	x.push_back(0);
	y.push_back(0);

	rep(i, n-1) {
	    int a, d;
	    cin >> a >> d;
	    x.push_back(x[a] + dx[d]);
	    y.push_back(y[a] + dy[d]);
	}
	cout << (*max_element(all(x)) - *min_element(all(x)) + 1) << ' ' 
	    << (*max_element(all(y)) - *min_element(all(y)) + 1) << endl;
    }

    return 0;
}

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

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

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

  int N, K;
  cin >> N >> K;
  
  cout << N - K + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()



int main() {
  int n;
  cin >> n;
  vector<int> a(100100);
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    a[x] = i;
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
  return 0;
}

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

int main() {
  int N, M, c[51]={0};
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int ai, bi;
    cin >> ai >> bi;
    c[ai]++;
    c[bi]++;
  }
  for (int i = 1; i <= N; i++) cout << c[i] << endl;
}


Measured memory_bytes: 256
N = int(input())
S = list(input())
ans = []
for i in range(len(S)+1):
    num = 0
    X = S[:i]
    Y = S[i:]
    xd = {}
    yd = {}
    for j in X:
        if j in xd:
            continue
        else:
            xd[j] = 1

    for j in Y:
        if j in yd:
            continue
        else:
            yd[j] = 1


    for k in xd:
        if k in yd:
            num += 1

    ans.append(num)

print(max(ans))
        

Measured memory_bytes: 3064
#pragma comment(linker, "/STACK:1000000000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <memory>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <ctime> 
#include <stack>

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 200001;

int a[MAXN];

int main()
{
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	ll sa = 0;
	int block;
	for (int i = 0; i < n; i++)
	{
		if (2ll * sa < a[i]) block = i;
		sa += a[i];
	}
	cout << n - block << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define debug printf("test\n")
int main()
{
	//ios::sync_with_stdio(0),cin.tie(0);
	int n , w;
	cin >> n >> w;
	vector<int> wi(n+1);
	vector<int> vi(n+1);
	wi[0] = 0;
	vi[0] = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> wi[i] >> vi[i];
	}
	long long dp[n+1][w+1];
	for (int i = 0; i <=n; i++)
	{
		dp[i][0] = 0;
	}
	
	for (int i = 0; i < w+1; i++)
	{
		dp[0][i] = 0;
	}
	
	for(int i = 1;i<=n;i++){
		for (int j = 1; j <= w ; j++)
		{
			if(j < wi[i]) dp[i][j] = dp[i-1][j];
			else {
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi[i]]+vi[i]);
			}
		}
	}
	cout << dp[n][w] << endl;
}


Measured memory_bytes: 79104
import math
from _functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)

print(ans)

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

template<class M>
struct SegTree {
    using T = typename  M::T;
    int sz;
    vector<T> seg;
    SegTree(int n) {
        sz = 1;
        while(sz < n) sz <<= 1;
        seg.assign(2*sz, M::e());
    }

    void build(){
        for(int i = sz-1; i > 0; --i){
            seg[i] = M::f(seg[2*i], seg[2*i+1]);
        }
    }
    void update(int k, const T &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = M::f(seg[2*k], seg[2*k+1]);
        }
    }

    T query(int a, int b){
        T l = M::e(), r = M::e();
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1) l = M::f(l, seg[a++]);
            if(b & 1) r = M::f(seg[--b], r);
        }
        return M::f(l, r);
    }
};

struct Monoid {
    using T = int;
    static T f(T a, T b){ return min(a, b); }
    static T e() { return 1000000007; }
};
int main() {
    string s;
    cin >> s;
    vector<vector<int>> v(s.size()*2+1);
    int offset = s.size();
    v[offset].emplace_back(0);
    ll val = 0, cur = 0, x = 0;
    vector<int> xs;
    SegTree<Monoid> seg(offset);
    seg.update(0, x);
    vector<int> vals;
    for(auto &&c : s){
        if(c == '-'){
            val -= vals.back();
            vals.pop_back();
            v[x+offset].pop_back();
            x -= xs.back();
            xs.pop_back();
            cur--;
        }else {
            cur++;
            x += (c == '(' ? 1 : -1);
            xs.emplace_back((c == '(' ? 1 : -1));
            v[x+offset].emplace_back(cur);
            int ng = -1, ok = v[x+offset].size()-1;
            while(ok-ng > 1){
                int mid = (ok+ng)/2;
                (seg.query(v[x+offset][mid], cur) >= x ? ok : ng) = mid;
            }
            vals.emplace_back(((int)v[x+offset].size()-1)-ok);
            val += ((int)v[x+offset].size()-1)-ok;
            seg.update(cur, x);
        }
        printf("%lld\n", val);
    }
    return 0;
}


Measured memory_bytes: 22592
row1=list(map(int,input().split()))
row2=list(map(int,input().split()))
row3=list(map(int,input().split()))
bingo=row1+row2+row3
num=int(input())
num_list=set()
for i in range(num):
  num_list.add(int(input()))

bingo_list=[[0,3,6],[1,4,7],[2,5,8],[0,1,2],[3,4,5],[6,7,8],[0,4,8],[2,4,6]]
num_list=list(num_list)
for i in num_list:
  if i in bingo:
    bingo[bingo.index(i)] = True

for i in bingo_list:
  if bingo[i[0]] ==True and bingo[i[1]] == True and bingo[i[2]] == True:
    print('Yes')
    break
  if i == [2,4,6]:
    print('No')



Measured memory_bytes: 3064
#include <stdio.h>
int main(void)
{
    int N,M;
    int i;
    int sum=0;
    
    scanf("%d",&N);
    scanf("%d",&M);
    
    int A[M];
    for(i=0;i<M;i++){
    scanf("%d",&A[i]);
    sum+=A[i];
    }
    if(N<sum)
        printf("%d\n",-1);
    else
        printf("%d\n",N-sum);
    
    return 0;
}

Measured memory_bytes: 1760
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;

int main() {
  
  int a,b,c,d,x;
  string s,ss,sss;
  
  int ans = 0;
  string anss = "";
  
  cin >> s >> ss;
  
  int ab [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  int result3 = std::max({a, b, c});
//--------------------------------------------------------------------------------

  if(s < ss) anss = "<";
  else if(s > ss) anss = ">";
  else anss = "=";
  
  cout << anss << endl;

}

Measured memory_bytes: 256
def main():
    N, M = map(int, input().split())
    pair = []
    for i in range(N):
        A, B = map(int, input().split())
        pair.append([A, B])
    pair.sort()
    count = 0
    money = 0
    now = 0
    while True:
        if pair[now][1] + count < M:
            money += pair[now][1] * pair[now][0]
            count += pair[now][1]
        else:
            money += (M - count) * pair[now][0]
            break
        now += 1
    print(money)


if __name__ == "__main__":
    main()


Measured memory_bytes: 20072
n = int(input())
monster = list(map(int, input().split()))
hero = list(map(int, input().split()))

cnt = 0
for i in range(n):
  beat = hero[i] - monster[i]
  if beat >= 0:
    cnt += monster[i]
    if beat - monster[i+1] >= 0:
      cnt += monster[i+1]
      monster[i+1] = 0
    else:
      cnt += beat
      monster[i+1] -= beat
  else:
    cnt += hero[i]
    monster[i] -= hero[i]
print(cnt)

Measured memory_bytes: 18624
#include<stdlib.h>
p(int*a,int*b){return*a-*b;}
int main () {
int f[1001];
int F[1001];
int N,i,V,d,count;
for(;~scanf("%d%d",&V,&d);){
  F[0]=2;
  F[1]=3;
  count = 1;
  for(i=2;i<V;i++)F[i]=(F[i-1]+F[i-2])%1001;
  for(i=0;i<V;i++)f[i]=F[i];
  qsort(F,V,4,p);
  for(i=1;i<V;i++)
    if(F[i]-F[i-1]>d-1)
      count++;
  printf( "%d\n" , count);
 }
 return 0;
}

Measured memory_bytes: 636
#include <cstdio>
#include <cstdint>
#include <numeric>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  int k;
  scanf("%d", &k);

  intmax_t res = 0;
  for (intmax_t a = 1; a <= k; ++a)
    for (intmax_t b = 1; b <= k; ++b)
      for (intmax_t c = 1; c <= k; ++c)
        res += std::__gcd(std::__gcd(a, b), c);

  printf("%jd\n", res);
}


Measured memory_bytes: 1724
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <set>
#include <iomanip>
using namespace std;

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

int main()
{
    int a,b;
    cin >> a >> b;
    cout << a*b << endl;

    return 0;
}


Measured memory_bytes: 3560
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;

int main() {
  vector<int> a(4);
  cin >> a[0] >> a[1] >> a[2] >> a[3];
  sort(a.begin(), a.end());
  if(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}



//EOF


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

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

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

  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());

  int64_t ans = a.at(0);
  int64_t cnt = 1;
  for (int i = 2; i < n; i += 2) {
    ans += a.at(i - cnt);
    if (i + 1 < n) ans += a.at(i - cnt);
    cnt++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4836
#include <cstdio>
#include <algorithm>
using namespace std;

bool check(int a, int b, int c) {
	int L[3] = {a, b, c};
	sort(L, L + 3);
	if (L[0] == L[1]) return false;
	if (L[1] == L[2]) return false;
	if (L[2] >= L[0] + L[1]) return false;
	if (L[0] <= L[2] - L[1]) return false;
	return true;
}

int main() {
	int N;
	scanf("%d", &N);
	int L[N];
	for (int i = 0; i < N; i++) scanf("%d", L + i);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				ans += check(L[i], L[j], L[k]);
			}
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 1728
#キャンディーと２人の子供
def ABC_47_A():
    A,B,C = map(int, input().split())

    if A > B and A > C:
        if A == B + C:
            print('Yes')
        else:
            print('No')
    elif B > A and B > C:
        if B == A + C:
            print('Yes')
        else:
            print('No')
    else:
        if C == A + B:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':

    ABC_47_A()

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int[] heights = new int[n];
        for (int i = 0; i < n; i++) {
            heights[i] = Integer.parseInt(sc.next());
        }
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
 
        for (int i = 1; i < n; i++) {
            for (int j=Math.max(i - k, 0); j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + Math.abs(heights[i] - heights[j]));
            }
        }
        System.out.println(dp[n - 1]);
    }
}

Measured memory_bytes: 49068
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define deb(x) cout << #x << " is " << x << "\n";

using namespace std;
using namespace __gnu_pbds;

const double PI = 2 * acos(0.0);
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string s;
    cin >>n >>s;
    int i = 0, j = 2, ans = 0;
    while(j < n){
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C')
            ans++;
        i++;
        j++;
    }
    cout <<ans;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
zougen = 2
ans = 0

for i in range(1,n):
    if i == n-1:
        if zougen == 2:
            ans += 1
        elif zougen == 0:
            if a[i]-a[i-1]<0:
                ans += 2
            else:
                ans += 1
        else:
            if a[i]-a[i-1] > 0:
                ans += 2
            else:
                ans += 1
    elif zougen == 2:
        if a[i]-a[i-1]>0:
            zougen = 0
        elif a[i]-a[i-1]<0:
            zougen = 1
        else:
            zougen = 2
    elif zougen == 0:
        if a[i]-a[i-1]<0:
            zougen = 2
            ans += 1
    elif zougen == 1:
        if a[i]-a[i-1]>0:
            zougen = 2
            ans += 1

if n == 1:
    ans = 1

print(ans)


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

int main(){
  int a, b;cin>>a>>b;
  a = (a+11)%13;
  b = (b+11)%13;
  if(a==b)cout<<"Draw"<<endl;
  else if(a>b)cout<<"Alice"<<endl;
  else cout<<"Bob"<<endl;
}


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

int main() {
  int n;cin>>n;
  int x=1,ans=0;
  for(int i=1;i<=n;i++){
    int t=i,cnt=0;
    while(1){
      if(t%2==1)break;
      t/=2;
      cnt++;
    }
    if(ans<cnt){
      ans=cnt;
      x=i;
  }
  }
cout<<x<<endl;
}

Measured memory_bytes: 3624
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

signed main(){
    int N,K;
    int c=0;
    cin>>N>>K;
    K=K*K;
    for(int i=0;i<N;i++){
        int x,y;
        cin>>x>>y;
        int d=x*x+y*y;
        if(d<=K) c++;
    }
    cout<<c<<endl;
}



Measured memory_bytes: 3068
N,M,Q = map(int,input().split())
c_sum = [[0 for j in range(N+1)] for i in range(N+1)]

for _ in range(M):
    L,R = map(int,input().split())
    c_sum[L][R] += 1


# 二次元累積和の計算
for i in range(N):
    for j in range(N):
        c_sum[i+1][j+1] += c_sum[i+1][j] + c_sum[i][j+1] - c_sum[i][j]

for _ in range(Q):
    p,q = map(int,input().split())
    print(c_sum[q][q] - c_sum[p-1][q] - c_sum[q][p-1] + c_sum[p-1][p-1])


Measured memory_bytes: 13420
//Volume0-0058
import java.util.Scanner;

class P {
	public double x;
	public double y;
	P(double x,double y){
		this.x = x;
		this.y = y;
	}
}

public class Main {

	public static void main(String[] args){

		//declare
		P        A,B,C,D;
		String[] s;
		String   result;

		//input
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        	s = sc.nextLine().split("\\s");
        	A = new P(Double.parseDouble(s[0]),Double.parseDouble(s[1]));
        	B = new P(Double.parseDouble(s[2]),Double.parseDouble(s[3]));
        	C = new P(Double.parseDouble(s[4]),Double.parseDouble(s[5]));
        	D = new P(Double.parseDouble(s[6]),Double.parseDouble(s[7]));

        	//calculate
        	if   (is_orthogonal(A,B,C,D)){result = "YES";}
        	else                         {result = "NO" ;}

        	//output
        	System.out.println(result);
        }
	}

	private static boolean is_orthogonal(P a,P b,P c,P d){
		P e = new P(a.x - b.x,a.y - b.y);
		P f = new P(c.x - d.x,c.y - d.y);
		if(dot(e,f) == 0){return true;}
		return false;
	}

	private static double dot(P a,P b){
		return a.x * b.x + a.y * b.y;
	}
}

Measured memory_bytes: 17328
#include "bits/stdc++.h"
using namespace std;
#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
typedef long long ll;

const int INF = 1e9 + 7;
const long long LLINF = 1e18;

int main() {
    string A, B, C;
    cin>>A>>B>>C;

    int ia=0, ib=0, ic=0;
    char now=A[0];
    ia++;
    while(ia<=A.size() && ib<=B.size() && ic<=C.size()){
        if(now=='a') {
            if(ia==A.size()){
                cout<<"A"<<endl;
                break;
            }
            now=A[ia];
            ia++;
        }
        else if(now=='b'){
            if(ib==B.size()){
                cout<<"B"<<endl;
                break;
            }
            now=B[ib];
            ib++;
        }
        else{
            if(ic==C.size()){
                cout<<"C"<<endl;
                break;
            }
            now=C[ic];
            ic++;
        }
    }
    return 0;
}

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



Measured memory_bytes: 2108
#include <stdio.h>
#include <limits.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))

long int dp [1000] [1000];//??´????????\??????
int n, m;
int d[1000], c[1000];//?????¢?????????
long int func(int place, int date){

	if (place == n){
		return 0;
	}
	else if (!dp[place][date]){
		if ((n - place) > (m - date))
			dp[place][date] = LONG_MAX;
		
		else {
			long int a = func(place + 1, date + 1) + d[place] * c[date], b = func(place, date + 1);
			dp[place][date] = MIN(a,b);
		}
		for (int i = 0; date >= i; i++){
			dp[place][i] = dp[place][date];
		}
	}
	return dp[place][date];
}

int main(){

	scanf("%d %d", &n, &m);
	for (int i = 0; n > i; i++) scanf("%d", &d[i]);
	for (int i = 0; m > i; i++) scanf("%d", &c[i]);
	printf("%d\n", func(0, 0));
	return 0;
}

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

int main(){
    int A,B;
    scanf("%d%d",&A,&B);
    int c1,c2,c3;
    c1=A+B;
    c2=A-B;
    c3=A*B;
    int max=std::max({c1,c2,c3});
    std::cout<<max<<"\n";
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000
#define long long long // for codeforces

int main(){
  string s;
  cin>>s;
  cout << bitset<3>(s).count() << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin>>N;
string S;
cin>>S;
int count = 0;
for(int i=0; i<=N-3; i++){
    if(S[i]== 'A' && S[i+1] == 'B' && S[i+2] == 'C') count++;
}
cout<<count<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9 + 5;
int main(){
	int N;
    cin >> N;
    vector<int> heights(N); 
    vector<int> dp(N, INF);
  for(int i = 0 ;i < N; i++){
  	cin >> heights[i];
  }
  dp[0] = 0;
  for(int i = 0; i < N; i++){
  	for(int j : {i + 1, i + 2}){
    	if(j < N){
        	 dp[j] = min(dp[j], abs(heights[i] - heights[j]) + dp[i]);
        }
    }
   
    
    
  }
  
  cout << dp[N-1] << endl;
  
  
}


Measured memory_bytes: 1024
import Data.Bits
import qualified Data.Vector.Unboxed as VU

modulus :: Int
modulus = 10 ^ 9 + 7

modulus' :: Integer
modulus' = 10 ^ 9 + 7

addMod :: Int -> Int -> Int
addMod x y = (x + y) `mod` modulus

mulMod :: Int -> Int -> Int
mulMod x y = (x * y) `mod` modulus

powMod :: Int -> Int -> Int
powMod _ 0 = 1
powMod n m
    | m .&. 1 == 0 = mulMod x x
    | otherwise = mulMod n . powMod n $ m - 1 where
          x = powMod n $ m `div` 2

createFacts :: Int -> VU.Vector Int
createFacts n =
  VU.scanl (\x y -> if x == 0 then 1 else mulMod x y) 1 (VU.enumFromTo 1 $ n - 1)


invFacts :: Int -> VU.Vector Int -> Int
invFacts 0 facts = 1
invFacts x facts =
  if x == 0 then 1 else powMod ((facts VU.! x) `mod` modulus) (modulus - 2)

cmb :: Int -> Int -> VU.Vector Int -> Int
cmb x y facts = (facts VU.! (x + y)) `mulMod` ((invFacts x facts) `mulMod` (invFacts y facts))

routesVia :: Int -> Int -> Int -> Int -> VU.Vector Int -> Int
routesVia x y w h facts =
  (cmb x y facts) `mulMod` (cmb x' y' facts)
  where
    x' = w - x
    y' = h - y

allRoutes :: Int -> Int -> Int -> Int -> VU.Vector Int -> Int
allRoutes h w a b facts =
  sum $ map (\x -> routesVia (b + x) (h - a - 1 - x) (w - 1) (h - 1) facts)  [0..min (h - a -1) (w - b - 1)]

main = do
  [h, w, a, b] <- map (read :: String -> Int) . words <$> getLine
  let facts = createFacts(h + w - 1)
  let r = allRoutes h w a b facts
  putStrLn $ show $ r `mod` modulus

Measured memory_bytes: 5116
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cassert>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define RREP(i,n) for(int i=(n)-1; i>=0; --i)
#define SREP(i,s,n) for(int i=(s), i##_len=(n); i<i##_len; ++i)


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

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

bool comp(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
}

struct UnionFind {
    vector<int> par;
    vector<int> rank;
    
    UnionFind(int n = 1) {
        init(n);
    }
    
    void init(int n = 1) {
        par.resize(n); rank.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
        }
    }
    
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    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 (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

#define MOD (1000000007)

int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ull N;
    string S;
    cin >> N >> S;
    if (S[0] == 'W' || S[2*N-1] == 'W') {
        cout << 0 << endl;
        return 0;
    }
    
    ull cnt = 1;
    
    vector<ll> A(2*N);
    A[0] = 1;
    ll c = 1;
    SREP(i, 1, 2*N) {
        if (S[i] == 'B') {
            if (c%2 == 0) {
                c++;
                A[i] = c;
            } else {
                A[i] = c;
                cnt = (cnt*c)%MOD;
                c--;
                
            }
        } else {
            if (c%2 == 0) {
                A[i] = c;
                cnt = (cnt*c)%MOD;
                c--;
                
            } else {
                c++;
                A[i] = c;
            }
        }
    }
    if (c != 0) {
        cout << 0 << endl;
        return 0;
    }
    
    REP(i, N) {
        cnt = (cnt*(i+1))%MOD;
    }
    
    cout << cnt << endl;
}


Measured memory_bytes: 2196
import std;
void main(){
  int n = readln.chomp.to!int;
  long[] as = readln.chomp.split.to!(long[]);
  int[long] ac;
  long ans;
  foreach(a; as){
    if(a !in ac) ac[a] = 0;
    ac[a] += 1;
    ans += a;
  }
  
  
  int q = readln.chomp.to!int;
  foreach(_; 0 .. q){
    long[] bc = readln.chomp.split.to!(long[]);
    long b = bc[0], c = bc[1];
    if(b !in ac) ac[b] = 0;
    if(c !in ac) ac[c] = 0;
    ac[c] += ac[b];
    ans += (c - b) * ac[b];
    ac[b] = 0;
    ans.writeln;
  }
}

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

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

const int MAX_N=100000;
const int MAX_V=1000000000;

int N;
int X[MAX_N];
int L[MAX_N];

void input(){
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d%d",&X[i],&L[i]);
	}
}
P ps[MAX_N];

int solve(){
	for(int i=0;i<N;i++){
		ps[i]=P(X[i]+L[i],X[i]-L[i]);
	}
	sort(ps,ps+N);
	int cur=-MAX_V;
	int ans=0;
	for(int i=0;i<N;i++){
		if(cur<=ps[i].second){
			ans++;
			cur=ps[i].first;
		}
	}
	return ans;
}

int main(){
	input();
	int ans=solve();
	printf("%d\n",ans);
	return 0;
}

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

using namespace std;

double a, b, h, m;
double pi = atan(1)*4;

void solve() {
  cin >> a >> b >> h >> m;
  double hPos = h+m/60.0;
  double mPos = m/5.0;
  double difference;
  
  double angle = (2.0*pi)/(12.0/abs(hPos-mPos));
  double ans = sqrt((a*a+b*b-2*a*b*cos(angle)));
  cout << setprecision(13) << (double)ans << '\n';
}

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

  solve();
  return 0;
}


Measured memory_bytes: 4232
#include<stdio.h>

int main(){
	int a, b;
	scanf("%d %d", &a, &b);
	while(a!=0 && b!=0){
		for(int i=0; i<a; i++){
			for(int j=0; j<b; j++){
				if(i==0 || j==0 || i==a-1 || j==b-1) printf("#");
				else printf(".");
			}
			printf("\n");
		}
		printf("\n");
		scanf("%d %d", &a, &b);
	}
}


Measured memory_bytes: 2604
#include <bits/stdc++.h>
using namespace std;
	 
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define cout_precision cout.setf(ios::fixed); cout.precision(32);
#define clr(a) memset(a,0,sizeof(a))
#define umap unordered_map
#define uset unordered_set
#define fr first
#define sc second
#define pb push_back
#define M int(1e9+7)
#define endl '\n'	
#define largest(a,b,c) (a>b?(a>c? a:c):(b>c? b:c))
#define smallest(a,b,c) (a<b?(a<c? a:c):(b<c? b:c))	

using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;

 
int main(){
	fast_io; cout_precision;
	string str;	cin >> str;
	ll sum = 0;
	for(int i=0; i<str.size(); i++)	sum += (str[i]-'0');
	if(sum%9)	cout<<"No"<<endl;
	else	cout <<"Yes"<<endl;

	return 0;
}
	

Measured memory_bytes: 3776
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        
        if (str.length() == 19) {
            System.out.println("0 0 1000000000 1 0 1000000000");
            return;
        }
        while (str.length() != 18) {
            str = "0" + str;
        }
        
        String str1 = str.substring(0,9);
        String str2 = str.substring(9,18);
        int num1 = Integer.parseInt(str1) + 1;
        int num2 = 1000000000 - Integer.parseInt(str2);
        
        String str3 = Integer.toString(num1);
        String str4 = Integer.toString(num2);
        
        System.out.println("0 0 1000000000 1" + " " + str4 + " " + str3);
    }
}


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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t l, r;
  std::cin >> r >> l;

  std::vector<bool> l_b(64), r_b(64);
  int64_t l_msb, r_msb;

  for (int64_t i = 0; i < 64; i++) {
    const int64_t f = static_cast<int64_t>(1) << i;
    l_b[i] = (f & l) != 0;
    r_b[i] = (f & r) != 0;

    if (l_b[i]) {
      l_msb = i;
    }
    if (r_b[i]) {
      r_msb = i;
    }
  }

  int64_t ans = 0;
  constexpr int64_t mod = 1000000007;
  for (int64_t i = r_msb + 1; i < l_msb; i++) {
    int64_t tmp = 1;
    for (int64_t j = i - 1; 0 <= j; j--) {
      tmp *= 3;
      tmp %= mod;
    }
    ans += tmp;
    ans %= mod;
  }

  if (r_msb != l_msb) {
    int64_t t1 = 0, t2 = 1;
    for (int64_t i = r_msb - 1; 0 <= i; i--) {
      if (r_b[i]) {
        t1 *= 3;
        t1 %= mod;
      } else {
        t1 *= 3;
        t1 %= mod;
        t1 += t2;
        t1 %= mod;
        t2 *= 2;
        t2 %= mod;
      }
    }
    ans += t1;
    t1 %= mod;
    ans += t2;
    t2 %= mod;

    t1 = 0;
    t2 = 1;
    for (int64_t i = l_msb - 1; 0 <= i; i--) {
      if (!l_b[i]) {
        t1 *= 3;
        t1 %= mod;
      } else {
        t1 *= 3;
        t1 %= mod;
        t1 += t2;
        t1 %= mod;
        t2 *= 2;
        t2 %= mod;
      }
    }
    ans += t1;
    ans %= mod;
    ans += t2;
    ans %= mod;
  } else {
    int64_t t1 = 1, t2 = 0, t3 = 0, t4 = 0;
    // no, l-free, r-free, free.
    // r -- l
    for (int64_t i = l_msb - 1; 0 <= i; i--) {
      t4 *= 3;
      t4 %= mod;
      if (l_b[i] && r_b[i]) {
        t4 += t3;
        t4 %= mod;
        t3 *= 2;
        t3 %= mod;
      } else if (l_b[i] && !r_b[i]) {
        t4 += t3;
        t4 %= mod;
        t3 *= 2;
        t3 %= mod;
        t4 += t2;
        t4 %= mod;
        t2 *= 2;
        t2 %= mod;

        t3 += t1;
        t3 %= mod;
        t2 += t1;
        t2 %= mod;

      } else if (!l_b[i] && r_b[i]) {
        t1 = 0;
      } else {
        t4 += t2;
        t4 %= mod;
        t2 *= 2;
        t2 %= mod;
      }
    }
    ans += t1;
    ans %= mod;
    ans += t2;
    ans %= mod;
    ans += t3;
    ans %= mod;
    ans += t4;
    ans %= mod;
  }

  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        int count = 0;
        boolean sw = false;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        double dMax = Double.MIN_VALUE;
        double dMin = Double.MAX_VALUE;
        //
        Scanner sc = new Scanner(System.in);
        //int n = sc.nextInt();
        String s = sc.next();
        if (s.equals("a")) System.out.println("b");
        if (s.equals("b")) System.out.println("c");
        if (s.equals("c")) System.out.println("d");
        if (s.equals("d")) System.out.println("e");
        if (s.equals("e")) System.out.println("f");
        if (s.equals("f")) System.out.println("g");
        if (s.equals("b")) System.out.println("h");
        if (s.equals("h")) System.out.println("i");
        if (s.equals("i")) System.out.println("j");
        if (s.equals("j")) System.out.println("k");
        if (s.equals("k")) System.out.println("l");
        if (s.equals("l")) System.out.println("m");
        if (s.equals("m")) System.out.println("n");
        if (s.equals("n")) System.out.println("o");
        if (s.equals("o")) System.out.println("p");
        if (s.equals("p")) System.out.println("q");
        if (s.equals("q")) System.out.println("r");
        if (s.equals("r")) System.out.println("s");
        if (s.equals("s")) System.out.println("t");
        if (s.equals("t")) System.out.println("u");
        if (s.equals("u")) System.out.println("v");
        if (s.equals("v")) System.out.println("w");
        if (s.equals("w")) System.out.println("x");
        if (s.equals("x")) System.out.println("y");
        if (s.equals("y")) System.out.println("z");
        
        
        
        

        sc.close();
    }

    public class Pair<F,S>
    {
        private final F first;
        private final S second;

        Pair(F first,S second)
        {
            this.first = first;
            this.second = second;
        }

        public void print() { System.out.println("("+this.first+","+this.second+")"); }

        //get
        public F first() {return this.first;}
        public S second() {return this.second;}

        @Override
        public boolean equals(Object object)
        {
            if (object instanceof Pair)
            {
                Pair pair = (Pair)object;
                return this.first==pair.first && this.second==pair.second;
            }else
            {
                return false;
            }
        }

        @Override
        public int hashCode()
        {
            return Objects.hash(first,second);
        }
    }
}

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


class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer a[] = new Integer[n + 100];
    Integer rev[] = new Integer[n + 100];
    for (int i = 1; i <= n; i++) {
      a[i]  = sc.nextInt();
      rev[a[i]] = i;
    }
    for(int i = 1; i <= n; i++){
      System.out.println(rev[i]);
    }


  }
}


Measured memory_bytes: 68312
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n,k,q;
	cin>>n>>k>>q;
	vi in(n);
	rep(i,n)cin>>in[i];
	
	vp w(n);
	rep(i,n)w[i]={in[i],i};
	sort(all(w));
	int out=inf;
	rep(i,n){
		vi d(n,-1),co(n);
		int t=0;
		rep(j,n)if(in[j]<in[i])t++;
				else d[j]=t,co[t]++;

		vi r;
		rep(j,n)if(in[i]<=w[j].first&&co[d[w[j].second]]>=k)r.pb(w[j].first),co[d[w[j].second]]--;
		if(r.size()>q-1)out=min(out,r[q-1]-r[0]);
	}
	
	cout<<out<<endl;
}










Measured memory_bytes: 256
(defun input-line (str)
  (let ((res (make-array 2 :element-type 'integer
                           :fill-pointer 0
                           :adjustable t)))
    (progn (vector-push-extend (parse-integer (subseq str 0 1)) res)
           (vector-push-extend (parse-integer (subseq str 2 3)) res))
    res))

(defun judge-str (str ab)
  (let ((res #\T))
    (progn (if (not (eq (length str) (+ (aref ab 0) (aref ab 1) 1))) (setq res nil))
           (loop for i from 0 below (aref ab 0)
                 always (eq res #\T)
                 if (not (parse-integer (subseq str i (+ 1 i)) :junk-allowed t)) do (setq res nil))
           (if (and (eq res #\T) (not (eq (char str (aref ab 0)) #\-))) (setq res nil))
           (loop for i from (+ 1 (aref ab 0)) below (+ (aref ab 0) (aref ab 1) 1)
                 always (eq res #\T)
                 if (not (parse-integer (subseq str i (+ 1 i)) :junk-allowed t)) do (setq res nil)))
    res))

(let* ((atob (input-line (read-line)))
       (res (judge-str (read-line) atob)))
  (if (not (null res)) (format t "~a~%" "Yes") (format t "~a~%" "No")))

Measured memory_bytes: 6504
n, m = map(int, input().split())
c = [0] + list(map(int, input().split()))

INF = 1 << 29

# dp table 
NMAX = 500000
dp = [INF] * (NMAX + 1)

dp[0] = 0

for i in range(1, m + 1):
	for j in range(c[i], n + 1):
		dp[j] = min(dp[j], dp[j-c[i]] + 1)

print(dp[n])




Measured memory_bytes: 11036
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).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 (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

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


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int H, W; std::cin >> H >> W;
  std::vector<std::vector<char>> ans(2*H, std::vector<char>(W));
  rep(i,H) rep(j,W) std::cin >> ans[i*2][j];
  rep(i,H) rep(j,W) ans[i*2+1][j] = ans[i*2][j];

  rep(i,2*H) {
    rep(j,W) std::cout <<ans[i][j];
    std::cout << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int main ()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if (b+a==c+d)
    {
    	cout<<"Balanced"<<endl;
    		return 0;
    	}
	else if(b+a>c+d)
	{
		cout<<"Left"<<endl;
			return 0;
	}
	else
    {
    	cout<<"Right"<<endl;
    		return 0;
	}
	return 0;
}

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

using namespace std;


int main(){
	vector<vector<char> > matrix;
	char val;
	for(int i=0;i<3;i++){
		matrix.push_back(vector<char>());
		for(int j=0;j<3;j++){
			cin>>val;
			matrix[i].push_back(val);
		}
	}
	string res="";
	for(int i=0;i<3;i++){
		res=res+matrix[i][i];
	}
	cout<<res<<endl;




	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
as = gets.chomp.split.map(&:to_i)
bs = gets.chomp.split.map(&:to_i)
cs = gets.chomp.split.map(&:to_i)

present = as[0]
sum = 0
as.each do |a|
  a -= 1
  sum += bs[a]
  if a == present + 1
    sum += cs[present]
  end
  present = a 
end
puts sum

Measured memory_bytes: 1788
n = int(input())
isp = []

for i in range(n):
    s, p = input().split()
    isp.append([i + 1, s, int(p)]);

isp.sort(key=lambda x: x[2], reverse=True)
isp.sort(key=lambda x: x[1])

for v in isp:
    print(v[0])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=acos(-1);
const ll INF=1e15;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

const ll MXN=300000;
vl G[MXN];
vl ans(MXN,0);
vl d(MXN,0);

void dfs(ll x,ll y){
  ans[x]=y;
  ll k=G[x].size();
  if(k!=0){
    rep(i,k){
      if(ans[G[x][i]]==0){
        dfs(G[x][i],y+d[G[x][i]]);
      }
    }
  }
}

int main() {
  ll N;
  cin >> N;
  vl a(N);
  ll x;
  rep(i,N){
    cin >> a[i];
    if(i%2==1){
      x-=a[i];
    }
    else{
      x+=a[i];
    }
  }
  rep(i,N){
    if(i==0){
      cout << x << endl;
    }
    else{
      cout << 2*a[i-1]-x << endl;
      x=2*a[i-1]-x;
    }
  }
}

Measured memory_bytes: 13824
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

/* a と b の最大公約数を返す関数 */
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

const ll C_MAX = (ll)1e18;

int main()
{
	ll A;
	long double B;

	cin >> A >> B;
	A = A * (B * 100 + 0.05) / 100;

	cout << A << endl;
	
	return 0;
}

Measured memory_bytes: 3720
# coding: utf-8
# Your code here!
# 幅優先探索（行きがけ）
import collections
import sys
import copy
import re
import math


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    C = S()
    rcount = 0
    ans = 0
    for c in C:
        if c == "R":
            rcount += 1

    for r in range(rcount, N):
        if C[r] =="R":
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


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

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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    sort(d.begin(), d.end());
    int l=d.size()/2-1, r=d.size()/2;
    cout << d[r]-d[l] << endl;
    return 0;
}


Measured memory_bytes: 640
import sys
from collections import deque
input = sys.stdin.readline


def main():
    n,k = map(int,input().split())
    s = list(input())
    tank = []
    judge = True
    if s[0] == '0':
        judge = False
    cnt = 0
    for i in range(n):
        if judge:
            if s[i] == '0':
                tank.append(cnt)
                judge = False
                cnt = 0
            cnt += 1
        else:
            if s[i] == '1':
                tank.append(cnt)
                judge = True
                cnt = 0
            cnt += 1
        if i == n-1:
            tank.append(cnt)
    #print(tank)
    p = len(tank)
    if s[0] == '0' and (p+1)//2 <= k:
        print(n)
        exit()
    if p//2 <= k and s[0] == '1':
        print(n)
        exit()

    ans = 0
    res = 0
    if s[0] == '0':
        for j in range(2*k):
            res += tank[j]
        ans = res
        for j in range(2*k,p):
            if j == 2*k:
                res -= tank[0]
            elif j%2 == 0:
                res= res - tank[j-2*k] -tank[j-2*k-1]
            res += tank[j]
            ans = max(ans,res)

    else:
        for j in range(2*k+1):
            res += tank[j]
        ans = res
        for j in range(2*k+1,p):
            if j % 2 == 1:
                res = res- tank[j-2*k-1]-tank[j-2*k]
            res += tank[j]
            ans = max(ans,res)

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 5028