akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const int inf = 1e9;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;




int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;cin >> n;
    ll aary[n];
    ll bary[n];
    ll cary[n];
    rep(i,n) cin >> aary[i];
    rep(i,n) cin >> bary[i];
    rep(i,n) cin >> cary[i];
    sort(aary, aary+n);
    sort(bary, bary+n);
    sort(cary, cary+n, greater<int>());
    ll ans = 0;

    rep(i,n)
    {
        ll tmp_b = bary[i];
        int ok = -1;
        int ng = n;
        ll aans;
        ll cans;
        while(abs(ok-ng)>1)
        {
            int mid = (ok+ng)/2;
            if (cary[mid] > tmp_b)
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        cans  = ok + 1;

        ok = -1;
        ng = n;
        while(abs(ok-ng)>1)
        {
            int mid = (ok+ng)/2;
            if (aary[mid] < tmp_b)
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        aans = ok+1;
        // cout << endl;
        // cout << "cans " << cans << endl;
        // cout << "aans " << aans << endl;
        // cout << "ans " << ans << endl;

        ans += aans * cans;
    }
    cout<< ans << endl;
    
}


Measured memory_bytes: 2560
n = int(input())
p1 = 0
p2 = 0
for i in range(n):
    k , p = input().split()
    z = 0
    if k == p:
        p1,p2 = p1+1,p2+1
        continue
    elif len(k) <len(p):
        z = len(k)
    else:
        z = len(p)
    for i in range(z):
        if ord(k[i])<ord(p[i]):
           p2 += 3
           break
        elif ord(k[i])>ord(p[i]):
           p1 += 3
           break
    else:
        if len(k) < len(p):
            p2 +=3
        else:
            p1 +=3

print("%d %d" %(p1,p2))


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
#define int long long int
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=400015;
#define M 1000000007
#define double long double
#define BINF 100000000000000
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 15000001
#define deb(x) cout << #x << " " << x << "\n";
const int LG = 22;

int dp[1001][10001];
int a[N], b[N];
int n, h;
int foo(int pos, int sum){
	if(sum >= h)
		return 0;
	if(pos == n){
		if(sum >= h) return 0;
		return BINF;
	}
	if(dp[pos][sum] != -1) return dp[pos][sum];

	int res = BINF;

	res = min(res, b[pos] + foo(pos, sum + a[pos]));
	res = min(res, foo(pos + 1, sum));
	res = min(res, b[pos] + foo(pos + 1, sum + a[pos]));

	return dp[pos][sum] = res;
}

#undef int
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);

	
    cin >> h >> n;
    for(int i = 0; i < n; i++)
    	cin >> a[i] >> b[i];

    init(dp, -1);

    int ans = foo(0, 0);

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



Measured memory_bytes: 81280
#include<stdio.h>
int n, ans, i;
int d;
char D[101];
int main(){
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%d", &d);
    D[d]=1;
  }
  for(i=0; i<=100; i++){
    if(D[i]){ans++;}
  }
  printf("%d\n", ans);
}

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

int main()
{
ll n ;
cin >> n ;
vector<ll> a(n);
rep(i, n){
  cin >> a[i];
}
vector<vector<ll>> dp(n+1, vector<ll>(5,0) );
rep(i,n){
  dp[i+1][0]=dp[i][0]+a[i];
  ll r1=0;
  if(a[i]==0)r1=2;
  else r1=a[i]%2;
  dp[i+1][1]=min(dp[i][1]+r1,dp[i][0]+r1);
  ll r2=(a[i]+1)%2;
  dp[i+1][2]=min({dp[i][0]+r2,dp[i][1]+r2,dp[i][2]+r2});
  dp[i+1][3]=min({dp[i][0]+r1,dp[i][1]+r1,dp[i][2]+r1,dp[i][3]+r1});
  dp[i+1][4]=min({dp[i][0]+a[i],dp[i][1]+a[i],dp[i][2]+a[i],dp[i][3]+a[i],dp[i][4]+a[i]});
}
cout << *min_element(dp[n].begin(),dp[n].end()) << endl;
return 0;
}

Measured memory_bytes: 15872
#include<cstdio>
#include<cmath>
#include<climits>
#include<algorithm>
#include<sstream>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<list>
#include<map>
#include<vector>

using namespace std;


#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long
#define MOD 1000000007

#define IMIN INT_MIN;
#define IMAX INT_MAX;


int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	int begin;
	begin = 0;
	rep(i, n) begin = a[i] - begin;
	begin /= 2;
	vector<int> m(n);
	rep(i, n) {
		m[i] = 2 * begin;
		begin = a[i] - begin;
	}
	cout << m[0];
	rept(i, 1, n) cout << ' ' << m[i];
	cout << endl;



	return 0;
}



Measured memory_bytes: 2048
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**18]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

if dp[-1] == 10**18:
    print(-1)
else:
    print(dp[-1])

Measured memory_bytes: 42732
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector> 
#include <cstring>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
  
  
namespace io{
    const int L = (1 << 20) + 1;
     
    char buf[L], *S , *T, c;
      
    char getchar() {
        if(S == T) {
            T = (S = buf) + fread(buf, 1, L, stdin);
            return (S == T ? EOF : *S++);
        }
        return *S++;
    }
     
    int inp() {
        int x = 0, f = 1; char ch;
        for(ch = getchar(); !isdigit(ch); ch = getchar())
            if(ch == '-') f = -1;
        for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
        return x * f;
    }
     
    ll inp_ll() {
        ll x = 0; int f = 1; char ch;
        for(ch = getchar(); !isdigit(ch); ch = getchar())
            if(ch == '-') f = -1;
        for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
        return x * f;
    }
     
    char B[25], *outs=B+20, *outr=B+20;
    template<class T>
    inline void print(register T a,register char x=0){
        if(x) *--outs = x, x = 0;
         
        if(!a)*--outs = '0';
        else
            while(a)
                *--outs = (a % 10) + 48, a /= 10;
         
        if(x)
            *--outs = x;
         
        fwrite(outs, outr - outs , 1, stdout);
        outs = outr;
    }
};
  
using io :: print;
using io :: inp;
using io :: inp_ll;
const int maxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const int M = 100000;
const int INF = 1e9;
int a[maxN]; 

char s[maxN];
vector<int> p[maxN];
int main()
{
	scanf("%s",s+1);
	int n = strlen(s+1);
	if(s[1] != '1' || s[n] != '0')
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n/2;i++)
	{
		if(s[i] != s[n-i])
		{
			puts("-1");
			return 0;
		}
	}
	int lt = 1;
	
	for(int i=2;i<=n/2;i++)
	{
		if(s[i] == '1')
		{
			p[i].push_back(lt);
			for(int j=lt+1;j<i;j++)
			{
				p[i].push_back(j);
			}
			lt = i;
		}
	}
	p[n].push_back(lt);
	for(int i=lt+1;i<n;i++)
	{
		p[n].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(auto y:p[i])
		{
			printf("%d %d\n",i,y);	
		} 
	}
    return 0;
}

Measured memory_bytes: 9468
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));

            return;
        }

        public void Solve(ConsoleInput cin)
        {
            var S = cin.Read;

            var len = S.Length;

            for (int i = len - 2; ; i -= 2)
            {
                if (S.Substring(0, i / 2) == S.Substring(i / 2, i / 2))
                {
                    WriteLine(i);
                    break;
                }
            }
        }
    }

    public static class Extensions
    {
        public static string Reverse(this string sourse)
        {
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 13268
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

alias D = Tuple!(long, "sum", int, "i", int, "j", int, "k");

void main() {
    auto xs = readints;
    int x = xs[0], y = xs[1], z = xs[2], kk = xs[3];
    auto a = reads!long;
    auto b = reads!long;
    auto c = reads!long;

    a.sort!("a > b");
    b.sort!("a > b");
    c.sort!("a > b");
    auto pq = new BinaryHeap!(Array!D);
    bool[Tuple!(int, int, int)] used;
    pq.insert(D(a[0] + b[0] + c[0], 0, 0, 0));
    while (kk > 0) {
        auto d = pq.front;
        pq.popFront();
        if (tuple(d.i, d.j, d.k) in used) continue;

        writeln(d.sum);
        used[tuple(d.i, d.j, d.k)] = true;
        kk--;

        int i = d.i;
        int j = d.j;
        int k = d.k;
        if (i + 1 < a.length)
            pq.insert(D(a[i + 1] + b[j] + c[k], i + 1, j, k));
        if (j + 1 < b.length)
            pq.insert(D(a[i] + b[j + 1] + c[k], i, j + 1, k));
        if (k + 1 < c.length)
            pq.insert(D(a[i] + b[j] + c[k + 1], i, j, k + 1));
    }
}


Measured memory_bytes: 2684
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

int main(void) {

    string s; cin >> s;
    stack<char> sim;
    for (auto c : s) {
        if (c != 'B') {
            sim.push(c);
        } else {
            if (!sim.empty()) sim.pop();
        }
    }

    string ans = "";
    while (!sim.empty()) {
        ans += sim.top();
        sim.pop();
    }
    reverse(ans.begin(), ans.end());

    cout << ans << endl;

    return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

int main() {
  llong N;
  cin >> N;
  N %= 10;
  if (N == 3) {
    cout << "bon" << endl;
  }
  else if (N == 0 || N == 1 || N == 6 || N == 8) {
    cout << "pon" << endl;
  }
  else {
    cout << "hon" << endl;
  }

  return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ll long long int
#define FASTIO std::ios::sync_with_stdio(false);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf 1e18
#define g(x) cout<<x<<" "<<endl;
#define gg(x,y) cout<<x<<" & "<<y<<" "<<endl
#define jam(t) cout<<"Case #"<<t<<": "
#define ggg(x,y,z) cout<<x<<" & "<<y<<" & "<<z<<" "<<endl
#define all(x) x.begin(),x.end()
#define input_from_file  freopen("input.txt", "r", stdin);
#define mod 1000000007ll
#define sz 400005
#define bitcnt(x) __builtin_popcountll(x)
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}


bool bad[sz];
ll dp[sz];
ll n,k,c;
ll get(ll x){
    // trace(x);
    if(x>n)
        return 0;
    if(dp[x]!=-1)
        return dp[x];
    if(bad[x])
        return dp[x] = get(x+1);
    ll an = 1 + get(x+c+1);
    //an = max(an,get(x+1));
    return dp[x] = an;

}
void solve(){
    
    cin >> n >> k >> c;
    string s;
    cin >> s;
    string ss = ".";
    ss+=s;
    for(ll i=1;i<=n;i++){
        if(ss[i]== 'x')
            bad[i] = true;
    }
  //  trace(bad[5]);
    for(ll i=1;i<=n;i++)
        dp[i] = -1;
    // get(1);
    for(ll i=1;i<=n;i++)
        get(i);
    ll i=1;
    vector <ll> imp;
  //  trace(dp[6]);
    ll curr = 0;
    while(i <= n){
        //trace(i);
        if(bad[i])
        {
            i++;
            continue;
        }
        if(curr + dp[i+1] >= k)
        {
            curr++;
            i+=c+1;
            continue;
        }
        else
        {
            imp.pb(i);
            curr++;
            i+=c+1;
        }
    }
    for(auto it:imp)
        g(it);

}
int main()
{
#ifndef ONLINE_JUDGE
input_from_file
#endif
 
    FASTIO
    cin.tie(NULL);
    fflush(stdout);
    ll t = 1;
 //   cin >> t;
    for(ll tcase = 1;tcase <= t;tcase++){
        solve();
        
    }
return 0;
}

Measured memory_bytes: 13432
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#include<queue>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
typedef long long ll;
int main(){
	int n;
	cin >> n;
	map<int,int> M;
	int a;
	rep(i,n){
		cin >> a;
		++M[a];
	}
	int cnt = 0;
	for(auto &item: M) {
		if(item.second%2) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}



Measured memory_bytes: 4992
fun main(args:Array<String>){
    val line = readLine()!!.split(" ").map{it.toInt()}
    val n = line[0]
    val d = line[1]
    val list = mutableListOf<List<Int>>()
    for(i in 1..n){
        list.add(readLine()!!.split(" ").map{it.toInt()})
    }
    var result = 0
    for(i in 0..n-2){
        for(ii in i+1..n-1){
            var num = 0
            val a = list[i]
            val b = list[ii]
            for(iii in 0..d-1){
                num += (a[iii]-b[iii])*(a[iii]-b[iii])
            }
            for(x in 0..160){
                if(num == x*x){
                    result++
                    break
                }
            }
        }
    }
    println(result)
}

Measured memory_bytes: 37892
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  std::string S;
  
  cin >> S;
  
  if(S == "AAA" || S == "BBB"){
    cout << "No";
    
  }else{
  
  cout << "Yes";
    
  }
  
  return 0;
  
}

Measured memory_bytes: 256
function Main(input) {
	input = input.trim().split(" ").map((a)=>Number(a));
  var A = input[0];
  var B = input[1];
  if((B > 0 && B - A > B) || A == 0 || B == 0){
     console.log("Zero");
  }else if(A > 0 && B > 0){
     console.log("Positive");
  }else{
       if((B - A) % 2 == 1){
          console.log("Positive");
       }else{
          console.log("Negative");
       }
	}
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
# -*- coding: utf-8 -*-

from sys import stdin
    
def calc(s):
    ans0 = 0
    ans1 = 0
    num = 0

    for x in s:
        if num == 0:
            if x == '0':
                ans1 += 1
            else:
                ans0 += 1
        else:
            if x == '1':
                ans1 += 1
            else:
                ans0 += 1
        num = (num + 1) % 2

    return min(ans0,ans1)

def main():
    s = stdin.readline().rstrip()
    ans = calc(s)
    print(ans)
    
if __name__=='__main__':
    main()

Measured memory_bytes: 3188
#include <stdio.h>

int main (void){
    int m, n, N;
    int p[200]={};
    int i;
    int gap,sgap=0;
    int memo;
    
    do{
        scanf("%d %d %d", &m, &n, &N);
        if(!m)
            break;
        for(i=0;i<m;i++){
            scanf("%d",&p[i]);
        }
        
        for(;n<N+1;n++){
            gap = p[n-1] - p[n];
            if(gap >= sgap){
                sgap = gap;
                memo = n;
            }
        }
        printf("%d\n",memo);
        sgap = 0;
    }while(1);
    
    
    return 0;
}

Measured memory_bytes: 600
#include <algorithm>
#include <bitset>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define pb push_back
#define debug1(x) cerr << #x << " = " << x << '\n';
#define debug2(x, y) cerr << #x << " = " << x << "   " << #y << " = " << y << "\n";
#define _ ios_base::sync_with_stdio(0);cin.tie(NULL);

void solve() {
    ll d, t, s;
    cin >> d >> t >> s;
    ll di = s * t;
    if(di >= d) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
}

int main() {_
    int t = 1;
//    cin >> t;
    for(int i = 1; i<=t; i++) {
        solve();
    }
    return 0;
}


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

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

  int k[N+1];
  for(int i=1;i<=N;i++)k[i]=0;
  int line[3];
  int m;
  for(int i=1; i<N; i++){
    for(int j=i+1; j<=N; j++){
      line[0] = j - i;
      line[1] = abs(X-i)+abs(Y-j)+1;
      line[2] = abs(Y-i)+abs(X-j)+1;
      m=min(line[0],min(line[1],line[2]));
      k[m]++;
    }
  }
  for(int i=1; i<N; i++){
    cout << k[i] << endl;
  }

}

Measured memory_bytes: 3548
var input = ""
process.stdin.resume();
process.stdin.setEncoding('utf-8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
 
process.stdin.on('end', function() {
  input = input.split("\n");
  i = 0
  
  while (true) {
    arr = input[i].split(" ");
    if (arr[1] == "?") { break; }

    arr[0] = Number(arr[0]);
    arr[2] = Number(arr[2]);
 
    switch (arr[1]) {
      case "+":
        console.log(arr[0] + arr[2]);
        break;
      case "-":
        console.log(arr[0] - arr[2]);
        break;
      case "*":
        console.log(arr[0] * arr[2]);
        break;
      case "/":
        console.log(Math.floor(arr[0] / arr[2]));
        break;
    }
 
    i++;
  }
});

Measured memory_bytes: 7904
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		String s = sc.next();

		if(s.startsWith("keyence") || s.endsWith("keyence")) {
			System.out.println("YES");
			return;
		}
		String[] sArray = s.split("");
		String end = getEnd(sArray);
		if(s.endsWith(end)) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}

	private static String getEnd(String[] sArray) {
		String end = "keyence";
		if(!sArray[0].equals("k")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[1].equals("e")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[2].equals("y")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[3].equals("e")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[4].equals("n")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[5].equals("c")) {
			return end;
		}
		end = end.substring(1);
		if(!sArray[6].equals("e")) {
			return end;
		}
		end = end.substring(1);
		return end;
	}
}

Measured memory_bytes: 23508
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,m = map(int,input().split())
    xyz = [list(map(int,input().split())) for i in range(n)]
    anslist = []
    for i in range(8):
        cand = []
        for j in range(n):
            p = 0
            for k in range(3):
                if ((i>>k)&1):
                    p -= xyz[j][k]
                else:
                    p += xyz[j][k]
            cand.append(p)
        cand.sort(reverse = True)
        anslist.append(sum(cand[:m]))

    print(max(anslist))
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 5812
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

int main(){
	IO_STREAM;
	int N,T,A;	cin>>N>>T>>A;
	int H;
	ll mint=INF;
	int ans=0;
	rep(i,1,N+1){
		cin>>H;
		ll t=1000*T-H*6;
		if(ans==0 || abs(t-A*1000)<abs(mint-A*1000)){
			mint=t;
			ans=i;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3660
#include <iostream>

using namespace std;

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

    int A[200];
    int left=0,right=0;
    
    for(int i=0; i < M; i++)
    {
        cin >> A[i];

        // if(A[i] == 1)
        //     continue;
        if( X > A[i] )
            left++;
        else
            right++;
    }

    cout << min(left,right) << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main {
  


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	String s = sc.next();
      	int cnt = 0;
      	for(int i=0;i<=s.length()-3;i++){
        	if(s.charAt(i) == 'A' && s.charAt(i+1) == 'B' && s.charAt(i+2) == 'C'){
            	cnt++;
            }
        }
      	
      	System.out.println(cnt);
      	
		}
	}

Measured memory_bytes: 35744
// default code for competitive programming
// ver 3.1415 {{{

// Includes
#include <bits/stdc++.h>

// Defines
#define NAME(x) #x
#define SZ(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
#define FOR(i, e) for( int i = 0 ; i < (e) ; i++ )
#define ITER(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define REP(i, s, e) for(int i = (s); i <= (e); i++)
#define REPD(i, s, e) for(int i = (s); i >= (e); i--)
#define IOS ios_base::sync_with_stdio( 0 )
#define DEBUG 1
#define fst first
#define snd second
#define PB push_back
#ifdef ONLINE_JUDGE
#define FILE( fn ) \
    freopen(fn".in","r",stdin); \
freopen(fn".out","w",stdout);
#else
#define FILE( fn )
#endif

#ifdef AKAI
#define debug( ... ) fprintf( stderr , __VA_ARGS__ )
#else
#define debug( ... )
#endif

using namespace std;

// Typedefs
typedef double real;
typedef long long ll;
typedef pair<ll, int> pli;
typedef tuple<ll, int> tli;
typedef pair<int, int> pii;
typedef tuple<int, int> tii;
typedef unsigned long long ull;

// Some common const.
const double EPS = 1e-8;
const double Pi = acos(-1);

// Equal for double
bool inline equ(double a, double b)
{return fabs(a - b) < EPS;}

int _R( int& x ) { return scanf( "%d" , &x ); }
int _R( ll& x ) { return scanf( "%" PRId64 , &x ); }
int _R( double& x ) { return scanf( "%lf" , &x ); }
int _R( char* s ) { return scanf( "%s" , s ); }

int R() { return 0; }

  template< typename T1 , typename... T2 >
int R( T1& x , T2&... tail )
{
  int tmp = _R( x );
  return tmp + R( tail... );
}

  template< typename Iter , typename F >
inline void out( Iter s , Iter e , F of )
{
  bool flag = 0;
  for( Iter it = s ; it != e ; it++ )
  {
    if( flag ) printf( " " );
    else flag = 1;
    of( *it );
  }
  puts( "" );
}

// }}}
// start ~~QAQ~~

const int MAXN = 1e5+10;
const ll  INF  = 1000000000000000;

int n;
ll E , T;
ll x[ MAXN ];
ll dp[ MAXN ] , mn[ MAXN ];

inline ll f( int i ) {
  return T+dp[ i ]-x[ i ];
}

inline ll g( int i ) {
  return dp[ i ]-x[ i ]-2*x[ i+1 ];
}

int main() {
  R( n , E , T );
  REP( i , 1 , n ) R( x[ i ] );
  dp[ 0 ] = 0;
  deque<int> dq{ 0 };
  int j = 0;
  mn[ 0 ] = g( 0 );
  REP( i , 1 , n ) {
    while( SZ( dq ) && 2*x[ dq.front()+1 ] < 2*x[ i ]-T )
      dq.pop_front();
    while( j < i && 2*x[ j+1 ] < 2*x[ i ]-T ) j++;
    dp[ i ] = INF;
    if( SZ( dq ) ) dp[ i ] = x[ i ] + f( dq.front() );
    if( j > 0 ) dp[ i ] = min( dp[ i ] , 3*x[ i ] + mn[ j-1 ] );
    //printf( "%lld dp %d %lld j %d\n" , x[ i ] , i , dp[ i ] , j );
    while( SZ( dq ) && f( dq.back() ) >= f( i ) )
      dq.pop_back();
    dq.push_back( i );
    mn[ i ] = min( mn[ i-1 ] , g( i ) );
  }
  printf( "%lld\n" , dp[ n ] + E-x[ n ] );
}


Measured memory_bytes: 2816
#include<iostream>
#include<algorithm>
#include<vector>
#include<bitset>

using namespace std;

int N, M;
bool cE[701][701];

int color[701];

void dfs(int pos, int bef, bool now_color, pair<int, int>& cnt) {
	color[pos] = now_color ? 1 : 2;
	if (now_color)cnt.first++;
	else cnt.second++;
	for (int i = 0; i < N; i++) {
		if (!cE[pos][i])continue;
		if (i == bef)continue;
		if (color[i] != 0 && color[i] + color[pos] != 3) {
			//二部グラフではない
			cnt.first -= 114514, cnt.second -= 114514;
			break;
		}
		if (color[i] == 0) {
			dfs(i, pos, !now_color, cnt);
		}
	}
}

int main() {

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (i != j)cE[i][j] = true;

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		cE[u][v] = false, cE[v][u] = false;
	}

	vector<pair<int, int>> e;
	for (int i = 0; i < N; i++) {
		if (color[i] == 0) {
			pair<int, int> tmp;
			dfs(i, -1, true, tmp);
			if (tmp.first < 0 && tmp.second < 0) {
				cout << -1 << endl;
				return 0;
			}
			e.push_back(tmp);
		}
	}

	bitset<1000> dp;
	dp[0] = true;
	for (int i = 0; i < e.size(); i++) {
		auto tmp = (dp << e[i].first);
		tmp |= (dp << e[i].second);
		dp = tmp;
	}

	int ans = 1145141919;
	for (int i = 0; i <= N; i++) {
		if (dp[i]) {
			ans = min(ans, i * (i - 1) / 2 + (N - i) * (N - i - 1) / 2);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 768
# coding: utf-8


def solve(*args: str) -> str:
    N = list(map(int, '0' + (args[0])))
    k = int(args[1])

    d = len(N)-1
    F = [[0]*(k+1) for _ in range(d+1)]
    U = [[0]*(k+1) for _ in range(d+1)]

    U[0][0] = 1
    for i in range(1, d+1):
        for j in range(1, k+1):
            # set zero on i_th digit
            F[i][j-1] += F[i-1][j-1] + U[i-1][j-1]*(0 < N[i])
            U[i][j-1] += U[i-1][j-1]*(0 == N[i])

            # set non-zero on i_th digit
            F[i][j] += max(0, N[i]-1)*U[i-1][j-1] + 9*F[i-1][j-1]
            U[i][j] += U[i-1][j-1]*(0 < N[i])

    return str(sum(x[k] for x in F+U))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


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

typedef long long ll;
#define nl '\n' 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n; cin>>n;
    ll a[222222];
ll cnt[222222];
    ll sum = 0;
    
    for (int i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    ll q; cin>>q;
    for (int i = 0; i < n; i++)
    {
        sum+=a[i];
        cnt[a[i]]++;
    }
    

    
    for (int i = 0; i <q; i++)
    {
        ll x,y; cin>>x>>y;
        ll cur  = cnt[x];
        sum-=cur*x;
        cnt[x]=0;
        sum+=cur*y;
        cnt[y]+=cur;
        cout<<sum<<nl;
    }
    

    
}


Measured memory_bytes: 5220
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	string s;
	bool ans = false;
	int a, b, c;
	cin >> s;
	map<char, int>m;
	for (auto ss : s)m[ss]++;
	a = m['a'];
	b = m['b'];
	c = m['c'];
	int sl = s.size();
	if (sl == 2) {
		if (a != 2 && b != 2 && c != 2)ans = true;
	}
	else if (sl == 3) {
		if (a != 0 && b != 0 && c != 0)ans = true;
	}else{
		if (abs(a - b) < 2 && abs(a - c) < 2 && abs(b - c) < 2)ans = true;
	}

	if (ans) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}



Measured memory_bytes: 3712
n = int(input())

maxi = n // 100 +1
for i in range(maxi):
    if 100 * i == n:
        print(1)
        exit()
    for j in range(maxi -i):
        if 100*i+101*j == n:
            print(1)
            exit()
        for k in range(maxi-(i+j)):
            if 100*i+101*j+102*k == n:
                print(1)
                exit()
            for l in range(maxi-(i+j+k)):
                if 100*i+101*j+102*k+103*l == n:
                    print(1)
                    exit()
                for m in range(maxi-(i+j+k+l)):
                    if 100*i+101*j+102*k+103*l+104*m == n:
                        print(1)
                        exit()
                    for o in range(maxi-(i+j+k+l+m)):
                        if 100*i+101*j+102*k+103*l+104*m+105*o == n:
                            print(1)
                            exit()
print(0)

Measured memory_bytes: 43632
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N,K;cin>>N>>K;
  vector<long>A(N);long S=0;
  for(long i=0;i<N;i++){cin>>A[i];S+=A[i];}
  
  vector<long>D;
  for(long i=1;i*i<=S;i++)if(S%i==0){D.push_back(i);D.push_back(S/i);}
  sort(D.begin(),D.end(),greater<long>());  
  for(auto d:D){
    vector<long>R;long sr=0;
    for(long i=0;i<N;i++)if(A[i]%d!=0){R.push_back(A[i]%d);sr+=A[i]%d;}
    sort(R.begin(),R.end());
    long k=0;
    for(long i=0;i<R.size()-sr/d;i++)k+=R[i];
    if(k<=K){cout<<d;return 0;}
  }
}



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

const int N = 305;
const int mod = 1e9 + 7;

int n, a[N], f[N][N][N], inv[N], prd[N];

void add(int &x, int y) {
	x = (x + y) >= mod ? x + y - mod : x + y; 
}

int pw(int x, int y) {
	if (!y) return 1;
	int ret = pw(x, y >> 1); ret = 1LL * ret * ret % mod;
	if (y & 1) ret = 1LL * ret * x % mod; return ret; 
}

int C(int k, int n) {
	return 1LL * prd[n] * inv[k] % mod * inv[n - k] % mod;
}

int cal(int x) {
	return 1LL * C(2, x - 1) * prd[x - 3] % mod;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	prd[0] = 1; 
	for (int i = 1; i <= n; ++i) prd[i] = 1LL * i * prd[i - 1] % mod;
	inv[n] = pw(prd[n], mod - 2);
	for (int i = n; i >= 1; --i) inv[i - 1] = 1LL * inv[i] * i % mod;
	f[0][0][0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= i; ++k) {
				if (!f[i][j][k]) continue;
				add(f[i + 1][j][k], f[i][j][k]);
				if (a[i + 1] >= 2) {
					add(f[i + 1][j + a[i + 1] - 2][k + 1], 1LL * f[i][j][k] * prd[a[i + 1] - 1] % mod * C(a[i + 1] - 2, j + a[i + 1] - 2) % mod);
				}
			}
		}
	} 
	int res = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 3; j <= n; ++j) {
			if (!f[n][i][j]) continue;
			if (n == j && i == 0) {
				add(res, 1LL * f[n][i][j] * cal(j) % mod); continue;
			}
			if (n == j || i == 0) continue;
			int val = 1LL * inv[i - 1] * prd[n - j - 1] % mod * cal(j) % mod;
			for (int k = 1; k <= n; ++k) val = 1LL * val * inv[a[k] - 1] % mod;
			add(res, 1LL * val * f[n][i][j] % mod);
		}
	}
	cout << res;
}

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

const int INF = 1<<29;

int main(){
    int n, cost[9999], dum[2][10010];
    int* dp[2];
    dp[0] = dum[0]+5005;
    dp[1] = dum[1]+5005;
    scanf("%d", &n);
    for(int x = 0; x < n-1; x++){
        scanf("%d", cost+x);
    }
    fill(dum[0], dum[0]+10010, INF);
    fill(dum[1], dum[1]+10010, INF);
    dp[0][1] = 0;
    for(int x = 0; x < n-1; x++){
        for(int y = -n/2; y <= n/2; y++){
            if(dp[x&1][y] < INF){
                dp[(x+1)&1][y+1] = min(dp[(x+1)&1][y+1],
                        dp[x&1][y]);
                dp[(x+1)&1][-y+1] = min(dp[(x+1)&1][-y+1],
                        dp[x&1][y] + cost[x]);
            }
            dp[x&1][y] = INF;
        }
    }
    printf("%d\n", dp[(n-1)&1][0]);
    return 0;
}

Measured memory_bytes: 1140
#include <stdio.h>

//#include <iostream>
//#include <vector>
//#include <string.h>

#pragma warning (push)
#pragma warning (disable : 4996)
#define mod 1000000007;

//using namespace std;

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

    char ret[3];
    if (N % 2 == 1) {
        sprintf(ret, "%d", (int)(N / 2 + 1));
    }
    else {
        sprintf(ret, "%d", (int)(N / 2));
    }

    printf(ret);
}

#pragma warning (pop)

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
#define pi atan(1)*4
#define BS(x,xx) binary_search(x.begin(),x.end(),xx)
#define ALL(x) x.begin(),x.end()
int a[10000];
int b[10000];
int main()
{
	int n;cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		b[a[i]]=1;
	}
	sort(a,a+n);
	int re=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			for(int k=j+1;k<n;k++)
			{
				if((a[i]+a[j])>a[k]&&(a[j]+a[k])>a[i]&&(a[i]+a[k])>a[j]) re++;
			}
		}
	}
	cout<<re<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 //Compiler version g++ 6.3.0

bool prime[55560];
 void eratosthenes(int n){
 	memset(prime, 1, sizeof(prime));
 	prime[0] = prime[1] = 0;
 	for(int i = 0; i <= sqrt(n); i++){
 		if(prime[i]){
 			for(int j = 2; j <= n/i; j++){
 				prime[i*j] = 0;
 			}
 		}
 	}
 }
 int main()
 {
 	int N;
 	cin >> N;
 	
 	eratosthenes(55555);
 	
 	int cnt = 0;
 	for(int i = 6; i <= 55555; i+=5){
 		if(cnt == N) break;
 		if(prime[i]){
 			cout << i << ' ';
 			cnt++;
 		}
 	}
 	cout << endl;
 	return 0;
 }

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

using namespace std;

int main() {
    long long int A, B, K;
    cin >> A >> B >> K;
    if(A <= K) {
        K -= A;
        A = 0;
        if(B <= K) {
            B = 0;
        } else {
            B -= K;
        }
    } else {
        A -= K;
    }
    cout << A << " " << B << endl;
}

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

int main(int argc, char const* argv[])
{
    std::string in_str;
    std::cin >> in_str;

    bool zero = true;
    int reverse_num_zero = 0;
    for(auto s : in_str)
    {
        if(zero)
        {
            if(s != '0')
            {
                reverse_num_zero ++;
            }
        }
        else
        {
            if (s != '1')
            {
                reverse_num_zero ++;
            }
        }
        zero = !zero;
    }

    zero = false;
    int reverse_num_one = 0;
    for(auto s : in_str)
    {
        if(zero)
        {
            if(s != '0')
            {
                reverse_num_one ++;
            }
        }
        else
        {
            if (s != '1')
            {
                reverse_num_one ++;
            }
        }
        zero = !zero;
    }

    std::cout << std::min(reverse_num_zero, reverse_num_one) << std::endl;

    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

typedef  long long int lint;

#define rep(i, n) for (lint i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define P pair<int,int>
#define enld endl

vector<lint> prime_factorization(lint N) {
	//素因数分解して配列で返す
	vector<lint> R;
	if (N < 2)return R;
	for (lint i = 2; i * i <= N; i++) {
		while (N % i == 0) {
			R.push_back(i);
			N /= i;
		}
	}
	if (N != 1) {
		R.push_back(N);
	}
	return R;
}

lint power(lint x, lint n, lint m) {
	//(x^n)%mを返す
	lint res = 1;
	x %= m;
	while (n > 0) {
		if (n % 2 == 1) {
			res = res * x % m;
		}
		x = x * x % m;
		n /= 2;
	}
	return res;
}

lint gcd(lint a, lint b) {
	//aとbの最大公約数を返す
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	return gcd(a % b, b);
}

lint lcm(lint a, lint b) {
	//aとbの最小公倍数を返す
	return a / gcd(a, b) * b;
}

int main() {
	
	lint N;
	cin >> N;
	vector<lint>A(N);
	rep(i, N) {
		cin >> A[i];
	}
	lint ans = A[0];
	rep(i, N) {
		ans = lcm(ans, A[i]);
	}
	cout << ans << enld;
}


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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#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(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
vector<pLL>v;
LL ans[200009];
int main()
{
    LL h,n;
    cin>>h>>n;
    LL mx=0;
    for(LL i=0; i<n; i++)
    {
        LL x,y;
        cin>>x>>y;
        v.pb(mk(x,y));
        mx=max(mx,x);
    }
    sort(all(v));
//    reverse(all(v));
    for(LL i=1; i<=h; i++)
        ans[i]=INF;
    ans[0]=0;
//        for(int i=0;i<=h+mx;i++)cout<<ans[i]<<" ";
//        cout<<endl;
    for(LL i=0; i<n; i++)
    {
        //        cout<<v[i].ff<<"..........\n";
        for(LL j=1; j<=h; j++)
        {

            ans[j]=min(ans[j],ans[max(0LL,j-v[i].ff)]+v[i].ss);

        }
    }
    cout<<ans[h];
}





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

int h,w,n;

main()
{
        cin>>h>>w>>n;
        int sum=0;
        int a=h+w-1;
        rep(i,a)
        {
                if(h>w)
                {
                        sum+=h;
                        w--;
                }
                else
                {
                        sum+=w;
                        h--;
                }
                if(sum>=n)
                {
                        cout<<i+1<<endl;
                        return 0;
                }
        }
}


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

n, k = [int(x) for x in input().split()]

ans = []

for i in range(2, n + 1):
    ans.append([1, i])

dic2 = (n - 1) * (n - 2) // 2

if k > dic2:
    print(-1)
    sys.exit()

a = 2
b = 3
while k < dic2:
    ans.append([a, b])
    dic2 -= 1
    b += 1
    if b > n:
        a += 1
        b = a + 1
    if a >= n and dic2 > k:
        print(-1)
        sys.exit()
print(len(ans))
for i in ans:
    print(*i)



Measured memory_bytes: 43376
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <stdlib.h>
#include <cstdlib>
#include <math.h>
#include <set>
#include"queue"
#include <vector>
#define inf 107374182
#define M 10010001
#define ll long long
#define PII pair<int,int>
using namespace std;
const int N=200110;
ll mod=1e9+7;
ll dp[2010];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<3;i++)
	{
		dp[i]=0;
	}
	for(int i=3;i<=n;i++)
	{
		dp[i]=1;
		for(int j=i-3;j>=3;j--)
		{
			dp[i]=(dp[i]+dp[j])%mod; 
		}
	}
	printf("%lld\n",dp[n]);
}

Measured memory_bytes: 3832
h, w = map(int, input().split())
ans = 0
ans += (h // 2) * (w // 2) * 2
if h % 2 != 0:
    ans += w // 2
if w % 2 != 0:
    ans += h // 2
if h % 2 != 0 and w % 2 != 0:
    ans += 1
if h == 1 or w == 1:
    ans = 1
print(ans)

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

const int MAX_n = 1e5;
int n,q,b,e;
int AC[MAX_n];
string str;

int main()
{
	scanf("%d%d",&n,&q);
	cin >> str;
	for ( int i = 1 ; i < n ; i++ )
	{
		AC[i] = AC[i-1];
		if ( str[i-1] == 'A' && str[i] == 'C' )
			AC[i]++;
	}
	for ( int i = 0 ; i < q ; i++ )
	{
		scanf("%d%d",&b,&e);
		printf("%d\n",AC[e-1]-AC[b-1]);
	}
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <numeric>
#include <climits>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <utility>
#include <cctype>
#include <iterator>
////////////////////////////////////////////////
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
////////////////////////////////////////////////
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  int n, k;
  cin >> n >> k;
  vecint a(n, 0);
  REPe(e, a) cin >> e;
  if (n < 2*k) {
    REP(i, n) cout << n << " ";
    cout << endl;
    return 0;
  }
  vecint b(n, 0);
  REP(j, k) {
    REP(i, n) b[i] = 0;
    REP(i, n) {
      int l = max(0, i - a[i]);
      int r = i + a[i] + 1;
      b[l]++;
      if (r < n) b[r]--;
    }
    a[0] = b[0];
    for (int i = 1; i < n; i++) a[i] = a[i - 1] + b[i];
  }
  REPe(e, a) cout << e << " ";
  cout << endl;
}


Measured memory_bytes: 4768
#include<iostream>

using namespace std;
typedef long long int ll;
const int M=1e9+7;

int main(){
    ll n,k,s=0;
    cin>>n>>k;
    for(ll i=k;i<=n+1;i++){
        s+=i*(n-i+1)+1;
        //cout<<i*(n-i+1)+1<<endl;
        s%=M;
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<vector<ll>> v(n);
    rep(i, n)
    {
        int t, d;
        cin >> t >> d;
        v[t - 1].push_back(d);
    }
    rep(i, n)
    {
        sort(v[i].begin(), v[i].end(), greater<ll>());
    }
    priority_queue<ll> top;
    priority_queue<ll> other;
    priority_queue<ll, vector<ll>, greater<ll>> res;
    ll s = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            if (j == 0)
            {
                top.push(v[i][j]);
            }
            else
            {
                other.push(v[i][j]);
            }
        }
    }
    for (int i = 0; i < k; i++)
    {
        if (other.empty())
        {
            break;
        }
        ll t = other.top();
        s += t;
        other.pop();
        res.push(t);
    }
    for (ll i = 1; i <= k; i++)
    {
        if (top.empty())
        {
            break;
        }
        ll t = top.top();
        top.pop();
        s += t;
        if (res.size() + i > k)
        {
            ll r = res.top();
            s -= r;
            res.pop();
        }
        ans = max(ans, s + i * i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 6904
#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++)
#define MAX 9223372036854775807
#define MOD 1000000007
#define PI 3.1415926535

int main(void){
    ll a, b, n;
    cin >> a >> b >> n;

    //２項目が０になる時
    ll x = min(b - 1ll,n);
    ll ans_0 = (double)a / (double)b * (double)x;

    cout << ans_0 << endl;

    return 0;
}


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

int main(){
    vector<ll> a(2), b(2);
    cin >> a[0] >> a[1] >> b[0] >> b[1];
    ll ans = -1e18;
    rep(i, 2)rep(j, 2){
        ans = max(ans, a[i] * b[j]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624