akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {
    int a, b, c;
    int cnt = 0;

    cin >> a >> b >> c;        

    for(int i = a; i <= b; i++) {
        if (c%i == 0) cnt++;
    }
    
    cout << cnt << endl;
    return 0;

}


Measured memory_bytes: 3116
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C - Many Requirements
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 10;
const int MAX_M = 10;
const int MAX_Q = 50;

/* typedef */

/* global variables */

int as[MAX_Q], bs[MAX_Q], cs[MAX_Q], ds[MAX_Q];
int es[MAX_N];

/* subroutines */

int check(int u, int n, int v, int m, int q) {
  if (u >= n) {
    int sum = 0;
    for (int i = 0; i < q; i++)
      if (es[bs[i]] - es[as[i]] == cs[i]) sum += ds[i];
    return sum;
  }

  int maxsum = 0;
  for (int i = v; i < m; i++) {
    es[u] = i;
    int sum = check(u + 1, n, i, m, q);
    if (maxsum < sum) maxsum = sum;
  }

  return maxsum;
}

/* main */

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);

  for (int i = 0; i < q; i++) {
    scanf("%d%d%d%d", as + i, bs + i, cs + i, ds + i);
    as[i]--, bs[i]--;
  }

  int sum = check(0, n, 0, m, q);
  printf("%d\n", sum);
  return 0;
}


Measured memory_bytes: 3240
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;
const ll INF = 1e9;

#define rep(i, n) for(ll i = 0; i < n ; i++ )
#define For(i, a, b) for(ll i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const ll MAX_N = 10;

ll power_(ll a, ll power){
    ll value = 1;
    
    while(power != 0){
        if(power & 1) value = value * a;
        a = a * a;
        power = power >> 1;
    }

    return value;
}


int main(void){
    /* 75 = 5 * 5 * 3
       a and b and c are coprime each other and prime num.
       num75 = a ** 4 * b ** 4 * c ** 2
       or a ** 24 * b ** 2
       or a ** 14 * b ** 4
       or a ** 74
    */

    ll N;
    ll n_prime = 15;
    ll prime[n_prime] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
    ll prime_cnt[n_prime];
    rep(i, n_prime) prime_cnt[i] = 0;
    ll answer = 0;
    
    cin >> N;
    
    For(i, 1, N + 1){
        ll tmp = i;
        rep(k, 6){
            ll p;
            rep(j, n_prime){
                p = prime[j];
                if (power_(p, k) > 100) break;
                if (tmp % p == 0){
                    tmp /= p;
                    prime_cnt[j] ++;
                }
            } 
        }
    }

    ll cnt_cd[5] = {0,0,0,0,0};
    
    rep(i, n_prime){
        if (prime_cnt[i] >= 2) cnt_cd[0] ++;
        if (prime_cnt[i] >= 4) cnt_cd[1] ++;
        if (prime_cnt[i] >= 14) cnt_cd[2] ++;
        if (prime_cnt[i] >= 24) cnt_cd[3] ++;
        if (prime_cnt[i] >= 74) cnt_cd[4] ++;
    }

    answer += cnt_cd[4];
    answer += cnt_cd[3] * (cnt_cd[0] - 1);
    answer += cnt_cd[2] * (cnt_cd[1] - 1);
    answer += cnt_cd[1] * (cnt_cd[1] - 1) / 2 * (cnt_cd[0] - 2);

    cout << answer << endl;
    
    return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let x: usize = sc.get();
    let ans = match x {
        400..=599 => 8,
        600..=799 => 7,
        800..=999 => 6,
        1000..=1199 => 5,
        1200..=1399 => 4,
        1400..=1599 => 3,
        1600..=1799 => 2,
        1800..=1999 => 1,
        _ => panic!("error"),
    };
    println!("{}", ans);
}


Measured memory_bytes: 2140
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

int A,B,C,D,ans;

int main(void){
	cin>>A>>B>>C>>D;
	ans=min(B,D)-max(A,C);
	if(ans>=0)cout<<ans<<endl;
	else cout<<0<<endl;
	return 0;
}

Measured memory_bytes: 256
s = input()
acgt = 'ACGT'

max_len = 0
for i in range(len(s)):
    curr_len = 0
    for j in range(len(s) - i):
        if s[i + j] in acgt:
            curr_len += 1
        else:
            break
    if curr_len > max_len:
        max_len = curr_len
print(max_len)


Measured memory_bytes: 2940
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FSilverFoxVsMonster solver = new FSilverFoxVsMonster();
        solver.solve(1, in, out);
        out.close();
    }

    static class FSilverFoxVsMonster {
        public void solve(int testNumber, Scanner in, PrintWriter out) {

            int n = in.nextInt();
            long range = in.nextInt();
            long atk = in.nextInt();
            long[] point = new long[n];
            long[] health = new long[n];
            ArrayList<Pair> ph = new ArrayList<>();
            long ans = 0;
            for (int i = 0; i < n; i++) {
                ph.add(new Pair(in.nextInt(), in.nextInt()));
            }
            ph.sort(Comparator.comparing(i -> i.x));

            // out.println(ph.toString());


            long[] accAtk = new long[n + 1];
            Arrays.fill(accAtk, 0);
            // 残っているものについて、左から順に右に2Dの範囲で攻撃する.
            int nowToAtk = 0;
            while (nowToAtk != n) {
                accAtk[nowToAtk] = nowToAtk == 0 ? 0 : accAtk[nowToAtk - 1] + accAtk[nowToAtk];
                if (accAtk[nowToAtk] >= ph.get(nowToAtk).y) {
                    // すでに倒れている
                    nowToAtk++;
                    continue;
                }
                long key = ph.get(nowToAtk).x + 2 * range;
                long time = (ph.get(nowToAtk).y - accAtk[nowToAtk] - 1 + atk) / atk;
                int ng = -1;
                int ok = point.length;
                while (Math.abs(ok - ng) > 1) {
                    int mid = (ok + ng) / 2;
                    if (ph.get(mid).x > key) {
                        ok = mid;
                    } else {
                        ng = mid;
                    }
                }
                // out.println("ok:" + ok);
                accAtk[nowToAtk] += atk * time;
                accAtk[ok] -= atk * time;
                ans += time;
                nowToAtk++;
                // System.out.println(Arrays.toString(accAtk));

            }
            out.println(ans);

        }

    }

    static class Pair {
        public long x;
        public long y;

        public Pair(long x, long y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "Pair{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }

    }
}



Measured memory_bytes: 164508
import java.util.Scanner;

public class Main {

	public static void main (String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int sum = 0;

		String[] str = String.valueOf(n).split("");

		for (int i = 0; i < str.length; i++) {
			sum  += Integer.parseInt(str[i]);
		}

		if (n % sum == 0) {
			System.out.println("Yes");

		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

ll gcd (ll x, ll y) {
    if (x < y) swap(x, y);
    if (y == 0) return x;
    return gcd(x % y, y);
}

int main(){
    ll a,b;
    cin>>a>>b;
    ll g=gcd(a,b);
    
    ll ans=1;
    for(int i=2; i<=sqrt(g)+1; i++){
        if(g%i==0){
            ans++;
            while(g%i==0) g/=i;
        }
    }
    if(g!=1) ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

struct Edge{
    int a, b, cost;
    Edge(int a_, int b_, int cost_){
        a = a_;
        b = b_;
        cost = cost_;
    }
    bool operator<(const Edge& o) const {
        return cost < o.cost;
    }
};

int main() {
    int n;
    cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n));
    rep(i, n)rep(j, n)cin >> a[i][j];
    rep(k, n)rep(i, n)rep(j, n){
        if(a[i][j] > a[i][k] + a[k][j]){
            cout << -1 << endl;
            return 0;
        }
    }

    ll ans = 0;
    vector<Edge> es;
    rep(i, n)rep(j, n){
        if(i >= j)continue;
        Edge e(i, j, a[i][j]);
        ans += a[i][j];
        es.push_back(e);
    }

    for(Edge e : es){
        int dist = e.cost;
        int v = e.a;
        int t = e.b;
        rep(i, n){
            if(v == i || t == i)continue;
            if(a[v][i] + a[i][t] == dist){
                ans -= dist;
                break;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1920
import sys


def main():
    n_list = [int(s) for s in sys.stdin.readline().strip().split()]
    n = n_list[0]
    a = [int(s) for s in sys.stdin.readline().strip().split()]
    b = [int(s) for s in sys.stdin.readline().strip().split()]

    ans = 0
    carry = 0
    for i in range(n):
        can_kill_max = carry + b[i]
        if a[i] < can_kill_max:
            ans += a[i]
            left_for_hero_i = a[i] - carry
            if left_for_hero_i > 0:
                carry = b[i] - left_for_hero_i
            else:
                carry = b[i]
        else:
            ans += can_kill_max
            carry = 0
    ans += min(carry, a[n])
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 76416
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
const int mod = 1000000007;
const int MAXV =  3502;

int main() {
  int n;
  cin >> n;
  vector<pair<pair<string, int>, int>> p(n);
  rep(i, n) {
    string a;
    int v;
    cin >> a >> v;
    p[i] = make_pair(make_pair(a, -v), i);
  }
  sort(p.begin(), p.end());
  rep(i, n) {
    cout << p[i].second + 1 << endl;
  }
}

Measured memory_bytes: 256
var a,b,d:Longint;
begin
read(a,b);
if(a<=0)and(0<=b)then writeln('Zero')else if 0<a then writeln('Positive')else begin
d:=b-a+1;
if b>0 then d:=-a;
if d mod 2=0 then writeln('Positive')else writeln('Negative')end end.

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define MAXN 15
#define MAXM 1000010
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
typedef long long LL;

int n,m,cnt[MAXN];
bool Map[MAXN][MAXN];
double f[2][2000][MAXN][2];

void Init()
{
    int i,u,v;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d",&u,&v); --u; --v;
        Map[u][v]=Map[v][u]=true;
        ++cnt[u]; ++cnt[v];
    }
}

void DP()
{
    int i,u,v,k,t,c;
    double ans=0,pre=0;
    f[0][1][0][1]=1;
    for(k=t=1;;k^=1,++t){
        memset(f[k],0,sizeof(f[k]));
        for(i=1;i<(1<<n)-1;++i)
            for(u=0;u<n;++u){
                if(!((1<<u)&i)) continue;
                for(v=0;v<n;++v){
                    if(!Map[u][v]) continue;
                    f[k][i|(1<<v)][v][0]+=f[k^1][i][u][0]/cnt[u]+f[k^1][i][u][1]/cnt[u];
                    f[k][i|(1<<v)][v][1]+=f[k^1][i][u][1]/cnt[u];
                }
            }
        for(u=ans=0;u<n;++u){
            f[k][(1<<n)-1][u][0]+=f[k^1][(1<<n)-1][u][0];
            f[k][(1<<n)-1][u][1]+=f[k^1][(1<<n)-1][u][1];
        }
        for(u=ans=0;u<n;++u) ans+=f[k][(1<<n)-1][u][0];
        if(t>n&&fabs(ans-pre)<1e-7){
            if((++c)>100) break;
        }
        else c=0;
        pre=ans;
    }
    printf("%.6f\n",ans);
}

int main()
{
    Init();
    DP();
    return 0;
}

Measured memory_bytes: 3660
N, x = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
ans = 0

for ai in a[:-1]:
    if x >= ai:
        x -= ai
        if x >= 0:
            ans += 1
    else:
        break

if x == a[-1]:
    ans += 1
    
print(ans)

Measured memory_bytes: 3064
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

even,odd = map(int,input().split())
if even != 1 or odd != 1:
    numa = cmb(even,2)
    numb = cmb(odd,2)
    if even == 1 or even == 0:
        numa = 0
    if odd == 1 or odd == 0:
        numb = 0
    print(numa+numb)
else:
    print(0)





Measured memory_bytes: 3064
N = gets.to_i
S = gets.chomp
PS = S[0...N].codepoints.map{ |n| n - "a".ord + 1 }
SS = S[N..-1].reverse.codepoints.map{ |n| n - "a".ord + 1 }
M = 5

ans = 0
psn = {}
(0...2**N).each{ |comb|
  r = 0
  b = 0
  ri = 0
  bi = 0
  (0...N).each{ |i|
    if ((1 << i) & comb) > 0
      r += PS[i]*(1 << (ri*M))
      ri += 1
    else
      b += PS[i]*(1 << (bi*M))
      bi += 1
    end
  }
  rb = r + (b << (N*M))
  psn[rb] = (psn[rb] || 0) + 1
}

(0...2**N).each{ |comb|
  r = 0
  b = 0
  ri = 0
  bi = 0
  (0...N).each{ |i|
    if ((1 << i) & comb) > 0
      r += SS[i]*(1 << (ri*M))
      ri += 1
    else
      b += SS[i]*(1 << (bi*M))
      bi += 1
    end
  }
  br = b + (r << (N*M))
  ans = ans + (psn[br] || 0)
}

p ans


Measured memory_bytes: 42236
#include <iostream>

using namespace std;

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

  if (A == 1) A = 100;
  if (B == 1) B = 100;

  if (A == B) {
    cout << "Draw" << endl;
  } else if (A > B) {
    cout << "Alice" << endl;
  } else {
    cout << "Bob" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
 	int a, b;
 	cin >> a >> b;
 	if (a >= 13) cout << b << endl;
 	else if (a >= 6) cout << b/2 << endl;
 	else cout << 0 << endl;
 	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int a[4] = {10,50,100,500};
    int n;
    bool flag = true;
    while(cin >> n, n){
        int coin[4];
        int mcoin[4];

        cin >> coin[0] >> coin[1] >> coin[2] >> coin[3];

        n = coin[0] * 10 + coin[1] * 50 + coin[2] * 100 + coin[3] * 500 - n;
        for(int i = 3; i >= 0; i--){
            mcoin[i] = n / a[i];
            n -= mcoin[i] * a[i];
        }

        if(flag) flag = false;
        else cout << endl;
        for(int i = 0; i < 4; i++){
            if(coin[i] > mcoin[i]) cout << a[i] << ' ' << coin[i] - mcoin[i] << endl;
        }
    }
}


Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;

class Damondai
{
    static void Main()
    {
        var ab = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var A = ab[0];
        var B = ab[1];
        var ans = Solve(A - 1) ^ Solve(B);
        Console.WriteLine(ans);
    }
    static long Solve(long num)
    {
        if (num % 2 == 1) return Calc(num);
        else
        {
            if (num <= 0) return 0;
            return num ^ Calc(num - 1);
        }
    }
    static long Calc(long num)
    {
        return (num + 1) / 2 % 2;
    }
}

Measured memory_bytes: 13268
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Objects;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ZeroOneKnapsack solver = new ZeroOneKnapsack();
        solver.solve(1, in, out);
        out.close();
    }

    static class ZeroOneKnapsack {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int weightLimit = in.nextInt();
            Vec2i[] product = new Vec2i[n];
            int[][] dp = new int[n + 1][weightLimit + 1];

            for (int i = 0; i < n; i++) {
                product[i] = new Vec2i(in.nextInt(), in.nextInt());
                // (value, weight);
                Arrays.fill(dp[i], 0);
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j <= weightLimit; j++) {
                    if (j >= product[i].y) {
                        dp[i + 1][j] = Math.max(product[i].x + dp[i][j - product[i].y], dp[i][j]);
                    } else {
                        dp[i + 1][j] = dp[i][j];
                    }
                }
            }

            out.println(dp[n][weightLimit]);

        }

    }

    static class Vec2i {
        public int x;
        public int y;

        public Vec2i(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "Vec2i{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vec2i vec2i = (Vec2i) o;
            return x == vec2i.x &&
                    y == vec2i.y;
        }

        public int hashCode() {
            return Objects.hash(x, y);
        }

    }
}




Measured memory_bytes: 31276
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
#n,t = [int(i) for i in readline().split()]
#a = [int(i) for i in readline().split()]
s = input()

g = p = 0
ans = 0
for i in s:
    if i == "g":
        if g > p:
            ans += 1
            p += 1
        else:
            g += 1
    else:
        if g > p:
            p += 1
        else:
            ans -= 1
            g += 1



print(ans)

Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
vector<int> v[100010];
int n;
int DFS(int x,int from){
	int xors=0;
	lol(i,v[x].size()){
		int to=v[x][i];
		if(to==from)continue;
		xors^=DFS(to,x)+1;
	}
	return xors;
}
int main(){
	cin>>n;
	lol(i,n-1){
		int a,b;cin>>a>>b;a--,b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	cout<<(DFS(0,0)?"Alice":"Bob")<<endl;
	return 0;
}


Measured memory_bytes: 11904
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = c - (a - b);
    if (ans < 0) {
        ans = 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3492
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

const int N = 110;
int n, k, a[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin >> k >> n;

	for(int i = 1; i <= n; i++) cin >> a[i];

	sort(a + 1, a + n + 1);
		
	int rest = k - a[n];
	int tot = k - 1;
	// dbg(rest);
	int ans = max(tot - 2 * rest, 0);
	if(k % 2 == 1) {

	}

		cout << ans << '\n';

}	




Measured memory_bytes: 256
n = int(input())
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

dp = [[0]*3 for i in range(n)]
dp[0][0] = a[0]
dp[0][1] = b[0]
dp[0][2] = c[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + a[i]
    dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + b[i]
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + c[i]

print(max(dp[-1]))

Measured memory_bytes: 34676
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}

//const MAX:usize = 100006;
//const INF:u64 = u64::max_value();

fn main() {
    let a:i32 = read();
    let b:i32 = read();

    println!("{}", if b%a==0 {a+b} else {b-a});

}


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


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	VI a(n+2);
	a[0] = a[n+1]= 0;
	rep(i, n) cin >>a[i+1];
	n+=2;
	int sm = 0;
	rep2(i, 1, n+1) sm += abs(a[i] - a[i-1]);
	rep2(i, 1, n-1){
		int w = sm;
		w -= abs(a[i]-a[i-1]) + abs(a[i+1]-a[i]);
		w += abs(a[i-1] - a[i+1]);
		cout <<w <<"\n";
	}
	return 0;


}


Measured memory_bytes: 1664
#include <iostream>
#include <queue>
#include <map>
#include <list>
#include <vector>
#include <string>
#include <stack>
#include <limits>
#include <cassert>
#include <fstream>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <ciso646>
#include <set>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define inf 0x3f3f3f3f
#define INF INT_MAX/3
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 2*acos(0.0)
#define INFILE() freopen("in0.txt","r",stdin)
#define OUTFILE()freopen("out0.txt","w",stdout)
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define FST first
#define SEC second
#define SETUP cin.tie(0), ios::sync_with_stdio(false), cout << setprecision(15)

namespace {
	struct input_returnner {
		int N; input_returnner(int N_ = 0) :N(N_) {}
		template<typename T> operator vector<T>() const { vector<T> res(N); for (auto &a : res) cin >> a; return std::move(res); }
		template<typename T> operator T() const { T res; cin >> res; return res; }
		template<typename T> T operator - (T right) { return T(input_returnner()) - right; }
		template<typename T> T operator + (T right) { return T(input_returnner()) + right; }
		template<typename T> T operator * (T right) { return T(input_returnner()) * right; }
		template<typename T> T operator / (T right) { return T(input_returnner()) / right; }
		template<typename T> T operator << (T right) { return T(input_returnner()) << right; }
		template<typename T> T operator >> (T right) { return T(input_returnner()) >> right; }
	};
	template<typename T> input_returnner in() { return in<T>(); }
	input_returnner in() { return input_returnner(); }
	input_returnner in(int N) { return std::move(input_returnner(N)); }
}

void solve();
/// ---template---
signed main(void) {
	SETUP;
	solve();
	return 0;
}

const int MOD = 1e9 + 7;
void solve() {
	vector<int> cnt(3);
	vector<string> str = in(3);

	int cur = 0;
	while (1) {
		if (cnt[cur] == str[cur].size()) {
			cout << char('A'+cur) << endl;
			return;
		}
		cnt[cur]++;
		cur = str[cur][cnt[cur]-1] - 'a';
	}
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;

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

int m,nmin,nmax;
int p[100001];

int main(void){
	while(1){
		scanf("%d%d%d",&m,&nmin,&nmax);
		if(m==0 && nmin==0 && nmax==0)break;
		for(int i=1;i<=m;i++){
			scanf("%d",&p[i]);
		}
		sort(p,p+m+1);
		int val=-1,res=-1;
		for(int i=nmin;i<=nmax;i++){
			if(p[m-i+1]-p[m-i]>=val){
				res=i;
				val=p[m-i+1]-p[m-i];
			}
		}
		printf("%d\n",res);
	}
	return 0;
}

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

int main() {
  int n;
  cin>>n;
  for(int i=0; i<=n/4; i++){
    for(int j=0; j<=n/7; j++){
      if(4*i + 7*j == n) {
        cout<<"Yes";
        return 0;
      }
    }
  }
  cout<<"No";
}

Measured memory_bytes: 256
N=int(input())
W=[]

for i in range(N):
  W.append(input())

ans="Yes"
for j in range(1,N):
  if W[j] in W[:j]:
    ans="No"
    break
  else:
    if W[j][0]!=W[j-1][-1]:
      ans="No"
      break
      
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl

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

    vector<ll> t(n);
    map<ll,ll> a;
    for(int i = 0; i < n; i++){
        cin >> t[i];
        a[t[i]]++;
    }

    if(n%3==0){
        if(a.size()==3){
            vector<ll> num;
            for(auto itr = a.begin(); itr != a.end(); ++itr){
                num.push_back(itr->first);
            }
            if((num[0]^num[1]) == num[2] && a[num[0]]==n/3 && a[num[1]]==n/3 && a[num[2]]==n/3){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else if(a.size()==2){
            ll num;
            for(auto itr = a.begin(); itr != a.end(); ++itr){
                if(itr->first != 0){
                    num = itr->first;
                }
            }
            if(a[num] == 2*n/3 && a[0] == n/3){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }

        }else if(a.size()==1){
            if(a[0]>0){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }else{
            cout << "No" << endl;
        }
    }else{
        if(a.size()==1 && t[0]==0){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}


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

int main() {
    string S;
    cin >> S;
    rep(i, 3) {
        if (S[i] == S[i + 1]) {
            cout << "Bad" << endl;
            return 0;
        }
    }
    cout << "Good" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a;
  int n=a;
  int d=0;
  while(a>0){
    d+=a%10;
    a/=10;
  }
  if(n%d==0)cout << "Yes";
  else cout << "No";
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#define fi first
#define se second
#define pb(i) push_back(i)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define mes(a,b) memset(a,b,sizeof(a))
#define sbs(i,j) substr(i,j)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
const int inf = - INF;
const int mod = 1e9+7;
const double pi = acos(-1.0);

void output(int len,char c){
    rep(i,1,len)
        cout<<c;
}
int main(){
    std::ios::sync_with_stdio(false);
    int tx,ty,sx,sy;
    cin>>sx>>sy>>tx>>ty;
    int dx=tx-sx,dy=ty-sy;
    //path 1
    output(dy,'U'),output(dx,'R');
    //path 2
    output(dy,'D'),output(dx,'L');
    //path 3
    cout<<'L',output(dy+1,'U'),output(dx+1,'R'),cout<<'D';
    //path 4
    cout<<'R',output(dy+1,'D'),output(dx+1,'L'),cout<<'U';
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'
#define pi 3.1415926535897932384626433832
#define ll long long
using namespace std;
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / __gcd(a, b); }
bool isPrime(int n) {if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;}

void lok(){

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin>>t;
    vector<ll> pak(t);
    for(auto &u:pak) cin>>u;
    ll ras=1000;
    ll sahm=0;
    ll was;
    for(ll i=0;i<t;i++){
        if(pak[i]<pak[i+1]){
            was=ras/pak[i];
            sahm+=was;
            ras-=pak[i]*was;
        }
        else if(pak[i]>pak[i+1]){
            was=sahm*pak[i];
            ras+=was;
            sahm=0;
        }
    }
    if(sahm>0){
        ras+=sahm*pak[t-1];
    }
    cout<<ras<<endl;
    return 0;
}

Measured memory_bytes: 3652
import scala.io.StdIn
import Math.sqrt
/**
  * AOJ
  */
object Main {

  def main(args: Array[String]): Unit = {

    val i = StdIn.readLine().split(" ").map(_.toDouble)
    val x = i(0) - i(2)
    val y = i(1) - i(3)
    println(sqrt(x * x + y * y))
  }
}

Measured memory_bytes: 43712
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  vector<int> a(3);
  rep(i, 3) cin >> a[i];
  int k;
  cin >> k;
  int mv = -1;
  int index = 0;
  rep(i, 3) {
    if(mv<a[i]) {
      mv = a[i];
      index = i;
    }
  }
  rep(i, k) mv = mv*2;
  int sum = 0;
  rep(i, 3) {
    if(i != index) sum += a[i];
  }
  sum += mv;
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    char s;
    cin >> s;
    if(isupper(s)) cout << "A" << endl;
    else cout << "a" << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;

bool isSame(int n,int a[],int b[]){
	bool ans = true;
	for(int i=0;i<n;i++) if(a[i]!=b[i]) ans = false;
	return ans;
}

int main(){
	int N;
	while(cin>>N,N){
		int S[12];
		for(int i=0;i<N;i++) cin>>S[i];
		for(int i=0;;i++){
			int S_[12];
			for(int j=0;j<N;j++){
				int n = S[j], cnt = 0;
				for(int k=0;k<N;k++){
					if(n==S[k]) cnt++;
				}
				S_[j] = cnt;
			}
			if(isSame(N,S,S_)){
				printf("%d\n%d",i,S[0]);
				for(int j=1;j<N;j++) printf(" %d",S[j]); puts("");
				break;
			}
			memcpy(S,S_,sizeof(S));
		}
	}
}

Measured memory_bytes: 1148
n,c=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
data=[0]*(n+1)
for i in range(n):
    x,y=xy[i]
    data[i+1]=data[i]+y
data1=[0]*(n+1)
data2=[0]*(n+1)
for i in range(n):
    x,y=xy[i]
    data1[i+1]=data[i+1]-x
    data2[i+1]=data[i+1]-2*x
data=[0]*(n+1)
for i in range(n):
    x,y=xy[n-1-i]
    data[i+1]=data[i]+y
data3=[0]*(n+1)
data4=[0]*(n+1)
for i in range(n):
    x,y=xy[n-1-i]
    data3[i+1]=data[i+1]-(c-x)
    data4[i+1]=data[i+1]-2*(c-x)
for i in range(1,n+1):
    data1[i]=max(data1[i],data1[i-1])
    data2[i]=max(data2[i],data2[i-1])
    data3[i]=max(data3[i],data3[i-1])
    data4[i]=max(data4[i],data4[i-1])
ans=-float("inf")
for i in range(0,n+1):
    a=data2[i]+data3[n-i]
    b=data4[i]+data1[n-i]
    ans=max(ans,a,b)
print(ans)

Measured memory_bytes: 70616
N = int(input())
A = int(input())

sum = 0

while True:
  if sum > N:
    sum -= 500
    break
  sum += 500
  
for i in range(A):
  if sum < N:
  	sum += 1
if sum == N:
  print("Yes")
else:
  print("No")
  


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main(){
  int n, m;
  cin >> n >> m;
  double a[n], sum = 0;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    sum += a[i];
  }
  double ok = (double) sum / (4 * m);
  int count = 0;
  for(int i = 0; i < n; i++){
    if(ok <= a[i]){
      count++;
    }
  }
  if(count >= m){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}
	
  
  


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {


	final int MOD = 1000000007;


	public static void main(String[] args) {

		long ans = 0;
		Scanner sc = new Scanner(System.in);
		boolean f = false;

		int n = sc.nextInt();
//		int k = sc.nextInt();

		//-------------------------------------------------------------------------------------

		for(int i =1; i <= n; i++) {
			if(i%3 == 0 && i%5 == 0) {
				continue;
			}
			if(i%3 == 0) {
				continue;
			}
			if(i%5 == 0) {
				continue;
			}
			ans += i;
		}


		//-------------------------------------------------------------------------------------

//		if(f) {
//			System.out.println("Yes");
//		} else {
//			System.out.println("No");
//		}

		System.out.println(ans);

		sc.close();
	}
}

Measured memory_bytes: 35840
using System;
using System.Linq;
using System.Collections.Generic;

namespace ABC
{
    class ProgramD
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            var list = new List<(int, int)>();
            for (var i = 0; i < n; i++)
            {
                var inputs = Console.ReadLine().Split(" ");
                list.Add((int.Parse(inputs[0]), int.Parse(inputs[1])));
            }

            var result = true;

            list = list.OrderBy(a => a.Item2).ToList();

            var time = 0;
            for (var i = 0; i < n; i++)
            {
                time += list[i].Item1;
                if (time > list[i].Item2)
                {
                    result = false;
                    break;
                }
            }

            Console.WriteLine(result ? "Yes" : "No");
        }

    }
}


Measured memory_bytes: 53484
import java.util.*;
import java.lang.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int max = 0, second = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            if (max <= a[i]) {
                second = max;
                max = a[i];
            } else if (second < a[i]) {
                second = a[i];
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (a[i] != max) {
                System.out.println(max);
            } else {
                System.out.println(second);
            }
        }
    }
}

Measured memory_bytes: 91472
N,W = map(int,input().split())
v = [0] * (N)
w = [0] * (N)
for i in range(N):
    w_t,v_t = list(map(int,input().split()))
    v[i] = v_t
    w[i] = w_t

dp = [[0] * (W+1) for _ in range(N+1)]

for j in range(N):
    for k in range(1,W+1):
        if k >= w[j]:
            dp[j+1][k] = max(dp[j][k],dp[j][k-w[j]]+v[j])
        else:
            dp[j+1][k] = dp[j][k]

print(dp[N][W])
    

Measured memory_bytes: 120044
#include<bits/stdc++.h>
#define ll long long
#define mx 100002
#define int long long
#define endl "\n"
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fi first
#define se second
#define fr(i,a,b) for(int i=a;i<=b;i++  )
#define pii pair<int,int>
using namespace std;
pii f[mx];
signed main()
{
    IO;
    int n,m;
    cin>>n>>m;
    fr(i,0,n-1)cin>>f[i].fi>>f[i].se;
    sort(f,f+n);
    int left=m;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(left==0)break;
        if(left>f[i].se)
        {
            ans+=(f[i].se*f[i].fi);
            left-=f[i].se;
        }
        else
        {
            ans+=(left*f[i].fi);
            break;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
signed main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  long long n,a,b,c,d,win[110]={};
  cin>>n;
  for(int i=0;i<n*(n-1)/2;i++){
    cin>>a>>b>>c>>d;
    if(c>d) win[a]+=3;
    else if(c<d) win[b]+=3;
    else{
      win[a]++;
      win[b]++;
    }
  }
  long long rank[110];
  for(int i=1;i<=n;i++){
    rank[i]=1;
    for(int j=1;j<=n;j++){
      if(win[i]<win[j]){
	rank[i]++;
      }
    }
  }
  for(int i=1;i<=n;i++) cout<<rank[i]<<'\n';
  return(0);
}



Measured memory_bytes: 3128
#include <bits/stdc++.h>
#include <random>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define ld double
#define pld pair<ld,ld>
#define pii pair<int,int>
#define sqr(a) ((a)*(a))
#define all(v) v.begin(),v.end()

using namespace std;
//using namespace __gnu_pbds;

ll MOD = 998244353;
const ll INF = 1e18;
const ld E = 1e-18;
const ld PI=acos(-1);
mt19937_64 rnd(time(0));
ll p1 = 31, p2 = 37, p3 = 7, p4 = rnd() % 100 + 1, md1 = MOD, md2 = 998244353, md3 = 998244357, md4 = rnd() % 1000000000;

//using ord_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll n, m, T, a[1000001];

ll binpow(ll h, ll r, ll md = MOD)
{
    ll l = 1;
    while (r)
    {
        if (r & 1) l *= h;
        h *= h;
        //h %= md;
        r /= 2;
    }
    return l;
}

ll gcd(ll x, ll y)
{
    if (x < y) swap(x, y);
    while (x && y)
    {
        x %= y;
        swap(x, y);
    }
    return x + y;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen("capitals.in","r",stdin);
    //freopen("capitals.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++)
            for (int u = 1; u <= 100; u++)
                a[i*i+j*j+u*u+i*j+i*u+j*u]++;
    for (int i = 1; i <= n; i++)
        cout << a[i] << "\n";
    return 0;
}

/*
3
4 2
1 1
1 0
3 2
2 2

3 1
1 1
1 0
3 2

3 2
1 1
1 0
3 2
*/


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

#define DEBUG(x) cout<<#x<<": "<<(x)<<endl

int main(){
	int n;
	cin>>n;
	int sum = 0, mx = 0;
	REP(i,n){
		int a;
		cin>>a;
		sum += a; CHMAX(mx, a);
	}
	sum -= mx/2;
	cout<<sum<<endl;
	return 0;
}

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

using namespace std;

int main() {
    int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
    int x3,y3,x4,y4;
    x3 = x2 - (y2 - y1);
    y3 = y2 + (x2 - x1);

    x4 = x3 - (y3 - y2);
    y4 = y3 + (x3 - x2);

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}



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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
long long GCD(long long a, long long b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (b == 0) return a;
    else return GCD(b, a % b);
}
set<int> prime_factorize(int n) {
    set<int> res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.insert(p);
    }
    if (n != 1) res.insert(n);
    return res;
}



int main(){
    long long n;
    cin>>n;
    vector<int>a(n);

    rep(i,n)cin>>a[i];

    //long long setwise=a[0];
    //rep2(i,n-1){
    //    setwise=GCD(a[i],setwise);
    //}
    //cout<<setwise<<endl;
    
    set<int> tree;
    bool p=true;
    //vector<int> cnt(1000010,0);
    rep(i,n){
        //int k=1;
        //int tmp=a[i];
        /*
        while(a[i]>1){
            k++;
            if(a[i]%k==0){
                //見つかる
                if(tree.find(k)!=tree.end()){
                    p=false;
                    break;
                }
                else{
                    //見つからない
                    tree.insert(k);
                }
                while(a[i]%k==0)a[i]/=k;
            }
        }*/
        auto res=prime_factorize(a[i]);
        auto iter=res.begin();

        while(iter!=res.end()){
            //cnt[iter->first]++;
            //cnt[*iter]++;
            if(tree.find(*iter)!=tree.end()){
                p=false;
                break;
            }
            else{
                tree.emplace(*iter);
            }
            iter++;
        }
    }

    if(p){
        cout<<"pairwise coprime"<<endl;
    }
    else{
    long long setwise=a[0];
    rep2(i,n-1){
    setwise=GCD(a[i],setwise);
    }
    if(setwise==1){
        cout<<"setwise coprime"<<endl;
    }
    else {
        cout<<"not coprime"<<endl;
    }
    }

    // bool t=true;
    // rep2(i,1000010){
    //     if(cnt[i]==n){
    //         t=false;
    //         break;
    //     }
    // }
    // if(!t){
    //     cout<<"not coprime"<<endl;
    // }
    // else if(p){
    //     cout<<"pairwise coprime"<<endl;
    // }
    // else{
    //     cout<<"setwise coprime"<<endl;
    // }
    return 0;

}
/*


*/


Measured memory_bytes: 10756
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
const int MAX = 1000000;
const int MOD = 1000000007;

int main(){
	int n;
	cin>>n;
	vector<int> a(n);
	REP(i,n){
		cin>>a[i];
	}
	sort(ALL(a));
	bool flag=true;
	REP(i,n-1){
		if(a[i]==a[i+1]){
			flag=false;
			break;
		}

	}
	if(flag) OUT("YES");
	else OUT("NO");
	return 0;
}

Measured memory_bytes: 1024