akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}


int main(void){
  int n;
  cin>>n;
  cout<<((n+1)/2) / 1.0 / n<<endl;
  return 0;
}


Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll a, b, n;
  in(n);
  a = n / 100;
  b = n % 100;
  if(a < 13 && a != 0){
    if(b > 12 || b == 0)
      out("MMYY");
    else
      out("AMBIGUOUS");
  }
  else{
    if(b > 12 || b == 0)
      out("NA");
    else
      out("YYMM");
  }
  memi;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
int main(){
	int N,K,X,Y;
	cin>>N>>K>>X>>Y;
	int ans=0;
	if(K>N)cout<<N*X<<endl;
	else{
		cout<<X*K+Y*(N-K);
	}
}


Measured memory_bytes: 256
import math
N = int(input())
nsqrt = int(math.sqrt(N))
ans = 10**9
for i in range(1, nsqrt+1):
    if N % i == 0:
        stri = str(i)
        strdiv = str(N // i)
        ans = min(ans, max(len(stri), len(strdiv)))
print(ans)
# print(nsqrt)


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define rep(i, j) for (int i = 0; i < j; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using ull = unsigned long long;

int gcd(int x, int y);
int fac(ll n, vector<int> num);

const int INF = 1001001001;

//mint�p�̕ϐ� (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> w_num(n + 1);
    w_num[0] = 0;
    rep(i, n) {
        w_num[i + 1] = w_num[i];
        if (s[i] == 'E')
            w_num[i + 1]++;
    }

    int ans = INF;
    rep(i, n) {
        int num = 0;

        num += i - w_num[i];             //������萼�ɂ��Đ��������Ă�l�̐�
        num += w_num[n] - w_num[i + 1];  //������蓌�ɂ��ē��������Ă�l�̐�
        ans = min(num, ans);
    }

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

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

/*�f��������*/
//���색�C�u����
int fac(ll n, vector<int> num) {
    ll kazu = n;
    for (int i = 2; i <= sqrt(n); i++) {
        while (1) {
            if (kazu % i != 0) break;

            kazu /= i;
            num[i]++;
        }
    }
    if (kazu == n && n != 1) return 1;
    int ans = 0;
    if (kazu != 1) ans++;
    for (int i = 2; i <= sqrt(n); i++) {
        for (int j = 1; j <= num[i]; j++) {
            num[i] -= j;
            ans++;
        }
    }
    return ans;
}

Measured memory_bytes: 4824
import java.util.Scanner;

public class Main {
	static int[] array;

	public static boolean isMake(int m, int i) {
		if (array[i] == m) {
			return true;
		} else {
			if (i == array.length - 1) {
				return false;
			} else {
				return (isMake(m, i + 1)) ||
						(isMake(m - array[i], i + 1));
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		for (int i = 0; i < q; i++) {
			if (isMake(sc.nextInt(), 0)) {
				System.out.println("yes");
			} else {
				System.out.println("no");
			}
		}
	}
}


Measured memory_bytes: 26880
#include <stdio.h>

struct point {
	double x;
	double y;
};

int main(void) 
{
	int i, n;
	struct point A, B, C, D;
	double slope_AB, slope_CD;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y, &D.x, &D.y);

		slope_AB = (A.y - B.y) / (A.x - B.x);
		slope_CD = (C.y - D.y) / (C.x - D.x);

		if (slope_AB == slope_CD) {
			printf("YES\n");
		} else {
			printf("NO\n");
		}
	}
	return 0;
}

Measured memory_bytes: 620
def del_row(lines):
    if not lines:
        return
    erasable = []
    for idx, line in enumerate(lines):
        if all([c == '.' for c in line]):
            erasable.append(idx)
    for idx in erasable[::-1]:
        del lines[idx]


def del_col(lines):
    if not lines:
        return
    erasable = []
    for idx in range(len(lines[0])):
        col = [lines[i][idx] for i in range(len(lines))]
        if all([c == '.' for c in col]):
            erasable.append(idx)
    for idx in erasable[::-1]:
        for i in range(len(lines)):
            del lines[i][idx]


lines = []
H, W = [int(x) for x in input().split()]
for i in range(H):
    lines.append(list(input()))

del_row(lines)
del_col(lines)
for line in lines:
    print(''.join(line))


Measured memory_bytes: 3188
s = input()
t = input()
n = len(s)
m = len(t)
LCS = [[0 for _ in range(m+1)] for j in range(n+1)]

for i in range(n+1):
    for j in range(m+1):
        if i==0 or j==0:
            LCS[i][j] = 0
        elif s[i-1] == t[j-1]:
            LCS[i][j] = 1+ LCS[i-1][j-1]
        else:
            LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1])
i = n
j = m
st = []
while i>0 and j>0:
    if s[i-1]==t[j-1]:
        st.append(s[i-1])
        i-=1
        j-=1
    elif LCS[i][j-1]>LCS[i-1][j]:
        j-=1
    else:
        i-=1
ans = st[::-1]
a = ''.join(ans)
print(a)

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

    const int MOD = 1000000007;
    const double PI = acos(-1); 

    //long long
    using ll = long long;

    //出力系
    #define print(x) cout << x << endl
    #define yes cout << "Yes" << endl
    #define YES cout << "YES" << endl
    #define no cout << "No" << endl
    #define NO cout << "NO" << endl
    
    // begin() end()
    #define all(x) (x).begin(),(x).end()

    //for
    #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

    //最大公約数（ll）
    ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}

    //素因数分解
    vector<pair<ll, int>>factorize(ll n){
      vector<pair<ll, int>> res;
      for(ll i = 2; i * i <= n; ++i){
        if(n % i) continue;
        res.emplace_back(i, 0);
        while(n % i == 0){
          n /= i;
          res.back().second++;
        }
      }
    if(n != 1) res.emplace_back(n, 1);
    return res;
    }



  // // 二分探索(最小値を出す問題は疑う)
  // bool C(ll x){
  //     ll res = 0;
  //     for(int i = 0; i < N; ++i){
  // 		res += max(0ll, A[i]-x/F[i]);
  //     }
  //     return res <= K;
  // }

  //   ll binary_search(ll ok, ll ng){
  //     while(abs(ok - ng) > 1){
  //       ll mid = (ok + ng) / 2;
  //       if(C(mid)) ok = mid;
  //       else ng = mid;
  //     }
  //     return ok;
  //   }


  int main(){
    string S;
    cin >> S;
    if(S.size() == 2) print(S);
    else {
      reverse(all(S));
      print(S);
    }
  }

Measured memory_bytes: 256
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 AAddtion
    {
        public static void Main(string[] args)
        {
            new AAddtion().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
            var ans = 3 * Math.Pow(cin.ReadInt,2);
            WriteLine(ans);
        }
    }
}
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
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
using namespace std;
#define MAXSIZE 200
#define MAXL 100
typedef long long int lli;

int getDigitSum(int x);

int getAbs(int x);

int getMin(vector<int> v);

int main(){
    int x, y, z;
    cin >> x >> y >> z;

    int ans = (x - z) / (y + z);
    cout << ans << endl;
    return 0;
}

int getDigitSum(int x){
    int res = 0;
    while(x > 0){
        res += x % 10;
        x /= 10;
    }
    return res;
}

int getAbs(int x){
    return (x > 0)? x : -x;
}

int getMin(vector<int> v){
    int res = 40000;
    for(int i = 0; i < v.size(); i++){
        res = min(res, v[i]);
    }
    return res;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <limits.h>
using namespace std;

int main(){
  int n; cin >> n;
  int p, a = 0, b = 0;
  int ar[n];
  for(int i = 0; i < n; i++) ar[i] = i + 1;
  for(int i = 0; i < n; i++){
    cin >> p;
    int cnt = 0;
    int j;
    for(j = 0; j < n; j++){
      if(ar[j] < p) cnt++;
      else if(ar[j] == p) break;
    }
    ar[j] = 100;
    int x = 1;
    for(int j = 1; j < n - i; j++) x *= j;
    a += cnt * x;
  }
  for(int i = 0; i < n; i++) ar[i] = i + 1;
  for(int i = 0; i < n; i++){
    cin >> p;
    int cnt = 0;
    int j;
    for(j = 0; j < n; j++){
      if(ar[j] < p) cnt++;
      else if(ar[j] == p) break;
    }
    ar[j] = 100;
    int x = 1;
    for(int j = 1; j < n - i; j++) x *= j;
    b += cnt * x;
  }
  if(a >= b) cout << a - b << endl;
  else cout << b - a << endl;
  return 0;
}


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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = "";
            var line = new String[3];

            while (!string.IsNullOrEmpty(read = Console.ReadLine()))
            {
                line = read.Split();
                if (line[1] != "?")
                {
                    Console.WriteLine(calc(int.Parse(line[0]), int.Parse(line[2]), line[1]));
                }
            }
        }

        static int calc(int a, int b, string op)
        {
            if (op == "+")
            {
                return a + b;
            }
            else if (op == "-")
            {
                return a - b;
            }
            else if (op == "*")
            {
                return a * b;
            }
            else if (op == "/")
            {
                return a / b;
            }
            else
            {
                return 0;
            }

        }
    }
}



Measured memory_bytes: 15968
#include<bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < (int)(n); i++)
#define sum(a) accumulate(a.begin(),a.end(),0LL)
#define put(i) cout<<fixed<<i<<endl
using namespace std;
using ll = long long;

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

    stack<char> st;
    ll left = 0, right = 0;
    for(long long i = 0; i < n; i++){
        if(!st.empty() and st.top() == '('){
            if(s[i] == ')'){
                st.pop();
            }else{
                st.push('(');
            }
        }else if(s[i] == ')'){
            st.push(')');
        }else{
            st.push('(');
        }
    }

    while(!st.empty()){
        char tmp = st.top(); st.pop();
        if(tmp == '(') left++;
        else right++;
    }

    for(long long i = 0; i < right; i++){
        cout << '(';
    }
    cout << s;
    for(long long i = 0; i < left; i++){
        cout << ")";
    }
    cout << endl;

    //for(;!st.empty();) { cout << st.top(); st.pop();} cout << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

int n;
int nxt[N];
ll k;

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        scanf("%d", &nxt[i]);
    
    map<int, int> m;
    int pos = 1;
    m[pos] = 1;
    int cnt = 0;
    int ans = -1;
    while(1){
        pos = nxt[pos];
        cnt ++;
        if(cnt == k) { ans = pos; break; }
        if(m[pos] == 1) break;
        m[pos] = 1;
    }

    if(ans != -1) { cout << ans << endl; return 0; }
    k -= cnt;
   // cout << cnt << " " << pos << endl;
    int t = pos;
    vector<int> node;
    node.push_back(pos);
    cnt = 0;
    while(1){
        t = nxt[t];
        cnt ++;
        node.push_back(t);
        if(t == pos) break;
    }

    cout << node[k % cnt] << endl;

    return 0;
}

Measured memory_bytes: 11984
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
typedef long long ll;

const int INF = 1001001001;

int main(void) {
  int n, m, l;
  cin >> n >> m >> l;
  vector<vector<int>> dist(n, vector<int>(n, INF));
  rep(i, n) dist[i][i] = 0;
  rep(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    --a; --b;
    dist[a][b] = dist[b][a] = c;
  }

  rep(k, n) rep(i, n) rep(j, n) {
    chmin(dist[i][j], dist[i][k] + dist[k][j]);
  }

  vector<vector<int>> dist2(n, vector<int>(n, INF));
  rep(i,n) rep(j, n) {
    if(dist[i][j] <= l) dist2[i][j] = 1;
  }
  rep(k, n) rep(i, n) rep(j, n) {
    chmin(dist2[i][j], dist2[i][k] + dist2[k][j]);
  }

  int q;
  cin >> q;
  rep(qi, q) {
    int s, t;
    cin >> s >> t;
    --s; --t;
    int ans = dist2[s][t] - 1;
    if(dist2[s][t] == INF) ans = -1;
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

signed main()
{
	IO_OP;
	
	int n;
	cin >> n;
	bool ok = true;
	while(n--) {
		int t;
		cin >> t;
		if(t%2 == 0) {
			if(t % 3 && t % 5) ok = false;
		}
	}
	if(ok) cout << "APPROVED" << endl;
	else  cout << "DENIED" << endl;
	
}





Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define mp make_pair
#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int n, k, q, a[2010];

    V v;

    cin >> n >> k >> q;

    REP(i, n)
    cin >> a[i], v.push_back(a[i]);

    a[n] = -1;

    SORT(v);

    int res = INT_MAX;

    int j = 0;

    while (true)
    {
        V x;
        int l = 0;
        int r = 0;
        while (r <= n)
        {
            if (a[r] == -1)
            {
                if (r - l >= k)
                {
                    priority_queue<int, vector<int>, greater<int>> q;
                    for (int i = l; i < r; i++)
                        q.push(a[i]);

                    for (int i = r - l; i >= k; i--)
                    {
                        x.push_back(q.top());
                        q.pop();
                    }
                }
                l = r + 1;
            }

            r++;
        }

        SORT(x);

        if (x.size() < q)
            break;

        res = min(res, x[q - 1] - x[0]);

        for (int i = 0; i < n; i++)
            if (a[i] == v[j])
                a[i] = -1;
        j++;
    }

    cout << res << endl;

    return 0;
}

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

a.insert(0,[0,0,0])

can="Yes"
for i in range(n):
    kyori=abs(a[i+1][1]-a[i][1]) + abs(a[i+1][2]-a[i][2])
    dt=a[i+1][0] - a[i][0]
    if dt < kyori:
        can="No"
        break
    if dt%2 != kyori%2:
        can="No"
        break
print(can)

Measured memory_bytes: 27300
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
#include<iomanip>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%d%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(LL *array,int array_n,char middle=' '){
	for(int i=0;i<array_n;i++)printf("%lld%c",array[i],(i!=array_n-1?middle:'\n'));
}
void array_show(vector<int> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%d%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}
void array_show(vector<LL> &vec_s,int vec_n=-1,char middle=' '){
	if(vec_n==-1)vec_n=vec_s.size();
	for(int i=0;i<vec_n;i++)printf("%lld%c",vec_s[i],(i!=vec_n-1?middle:'\n'));
}

int main(){
	int n,m;
	int i,j,k;
	LL a,b,c;
	cin>>b;
	a=100;
	for(i=0;a<b;i++){
		a+=a/100;
	}
	cout<<i<<endl;
}

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

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define sz size()

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>void __f(const char* name, Arg1&& arg1){cout<<name<<" : "<<arg1<<"\n";}
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...);} 
#define traceloop(x,a) { cerr<<#a<<": "; for(ll ix=0;ix<x;ix++) cerr<<a[ix]<<" "; cerr<<endl; }

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

ll dp[maxn][2];
vector<int> g[maxn];

void add(ll &x, ll y)
{
	x += y;
	if(x >= mod)
		x -= mod;
}

void mul(ll &x, ll y)
{
	x = x * y % mod;
}

void dfs(int u, int par)
{
	//trace(u, par);
	ll white = 1;
	ll black = 1;
	
	for(auto v : g[u]) if(v != par)
		dfs(v, u);

	for(auto v : g[u]) if(v != par)
	{
		mul(black, dp[v][0]);
		mul(white, (dp[v][0] + dp[v][1]) % mod);
	}

	dp[u][0] = white;
	dp[u][1] = black;
	//trace(u, black, white);
}

int main()
{
	ios::sync_with_stdio(0);

	int i, j, k, n;
	cin>>n;
	memset(dp, 0, sizeof dp);
	for(i=0;i<n-1;++i)
	{
		int u, v;
		cin>>u>>v;
		u--;
		v--;
		g[u].pb(v);
		g[v].pb(u);
	}

	dfs(0, -1);

	cout << (dp[0][0] + dp[0][1]) % mod << "\n";

	return 0;
}

Measured memory_bytes: 14208
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
#include <map>
#include <ctime>
#include <cmath>
#include <string.h>
#define inf 0x7fffffff
using namespace std;
struct P
{
    int x,y,z;
};
vector<P> v[456];
int a,b,c,n,m,i,k,o[140010],d,e,dy[5]={0,0,-1,1,0},dx[5]={0,1,1,1,2};
int l[100100];
long long x[100],y,z;
//double u[20000],p[20000];
int j[200100];
//long long x=0,y=0,z[99];
//char r[10003000];
//deque<int> d;
//'1'==49;
string r,r1;

int f(int t,int w)
{
    if(t<w) swap(t,w);
    for(;w;)
    {
        int h=w;
        w=t%w;
        t=h;
    }
    return t;
}

int main()
{
    scanf("%d %d",&a,&b);
    for(int t=1;t<=a;t++)
    {
        scanf("%d",&o[t]);
        i=max(i,o[t]);
    }
    k=o[1];
    for(int t=2;t<=a;t++)
        k=f(k,o[t]);
    if(b%k==0&&b<=i) puts("POSSIBLE");
    else puts("IMPOSSIBLE");
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 114514
vector<int> X[MAX_N];int Group[MAX_N], N, Q, A, B, C;
int main() {
	cin >> N >> Q;
	for (int i = 0; i < MAX_N; i++) { X[i].push_back(i); Group[i] = i; }
	for (int i = 0; i < Q; i++) {
		cin >> A >> B >> C;
		int D = Group[B], E = Group[C];
		if (A == 0 && D != E) {
			if (X[D].size() >= X[E].size()) {
				for (int j = 0; j < X[E].size(); j++) {
					Group[X[E][j]] = D; X[D].push_back(X[E][j]);
				}
				X[E].clear();
			}
			else if (X[D].size() < X[E].size()) {
				for (int j = 0; j < X[D].size(); j++) {
					Group[X[D][j]] = E; X[E].push_back(X[D][j]);
				}
				X[D].clear();
			}
		}
		if (A == 1) {
			if (D == E) { cout << "1" << endl; }
			else { cout << "0" << endl; }
		}
	}
	return 0;
}

Measured memory_bytes: 8072
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}

#[allow(unused_macros)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn main() {
    let (x, y) = read!(usize, usize);
    println!("{}", x + y / 2);
}


Measured memory_bytes: 4352
from sys import stdin
N = int(input())
nums = list(map(lambda x: int(x), stdin.readline().split(' ')))
count = 0
for i in range(N-1):
    min = nums[i]
    min_id = i
    for j in range(i+1, N):
        if min > nums[j]:
            min = nums[j]
            min_id = j
    if i != min_id:
        nums[i], nums[min_id] = nums[min_id], nums[i]
        count += 1
output = ""
for i in nums:
    output += str(i) + ' '
print(output[:-1])
print(count)


Measured memory_bytes: 5604
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i <= n ; i++)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int a, b, k; cin >> a >> b >> k;
    int n = min(a, b);
    vector<int> A;
    FOR(i, 1, n) if(a % i == 0 and b % i == 0) A.push_back(i);
    whole(sort, A, greater<int>()); 
    cout << A[k - 1] << endl;

}

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

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


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


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

int main() {
  string S;
  cin >> S;
  
  if (S.at(0)=='R' && S.at(1)=='R' && S.at(2)=='R') {
    cout << 3 << endl;
  }
  else if (S.at(0)=='S' && S.at(1)=='S' && S.at(2)=='S') {
    cout << 0 << endl;
  }
  else if (S.at(0)=='R' && S.at(1)=='R' && S.at(2)=='S') {
    cout << 2 << endl;
  }
  else if (S.at(0)=='R' && S.at(1)=='S' && S.at(2)=='R') {
    cout << 1 << endl;
  }
  else if (S.at(0)=='S' && S.at(1)=='R' && S.at(2)=='R') {
    cout << 2 << endl;
  }
  else if (S.at(0)=='R' && S.at(1)=='S' && S.at(2)=='S') {
    cout << 1 << endl;
  }
  else if (S.at(0)=='S' && S.at(1)=='R' && S.at(2)=='S') {
    cout << 1 << endl;
  }
  else if (S.at(0)=='S' && S.at(1)=='S' && S.at(2)=='R') {
    cout << 1 << endl;
  }
}

Measured memory_bytes: 3480
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>0;--i)
#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Vi vector<int>
#define Vl vector<long long>
#define pb(a) push_back(a)
using namespace std;

typedef long long ll;
const int inf=1000000000;
const int np=1000000007;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main() {
	int p,m,c;
	cin>>p>>m>>c;
	cout<<p+m+c<<endl;

	return 0;
}



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

using namespace std;
using ll = long long;


int main()
{
    int n; cin >> n;
    vector<pair<ll,ll>> sa, ba;
    ll sum = 0;
    ll nin = 1e9 * 2; 
    for(int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        sum += a;
        if(a <= b)sa.emplace_back(a,b);
        else ba.emplace_back(a,b);
    }

    if((int)sa.size() == n) {
        cout << 0 << endl;
        return 0;
    }

    for(auto i : ba) {
        nin = min(nin, i.second);
    }

    cout << sum - nin << endl;



}

Measured memory_bytes: 3908
vals = list(map(int, input().split()))
n,k = vals[0], vals[1]

arr = list(map(int, input().split()))
arr = [arr[0]] + arr
dp = [0]*(n+1)

def get_val(a,b, const):
    mini = float('inf')
    for i,j in zip(a,b):
        curr = i + abs(const - j)
        if curr < mini:
            mini = curr
    return mini

for i in range(2,n+1):
    if i <= k:
        dp[i] = get_val(dp[:i-1], arr[:i-1], arr[i])
    else:
        dp[i] = get_val(dp[i-k:i], arr[i-k:i], arr[i])

print(dp[-1])


Measured memory_bytes: 14108
n,k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
h_sort = sorted(h)
ans = max(h)
for i in range(n-k+1):
    check = h_sort[i+k-1] - h_sort[i]
    ans = min(ans,check)
print(ans)

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

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	int l = k;
	for (int i = 0; i < k; i++) {
	    if (a + i <= b) cout << a + i << endl;
	}
	for (int i = b - a + 1 - k; i <= b - a; i++) {
	    if (k - 1 < i) cout << a + i << endl;
	}
	return 0;
}


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

typedef long long ll;

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

    int n; cin >> n;
    int maxn = -100000000;
    int minn = 100000000;
    ll sum = 0;
    for(int i=0;i<n;i++){
        int a; cin >> a;
        maxn = max(maxn,a);
        minn = min(minn,a);
        sum += a;
    }
    cout << minn << ' ' << maxn << ' ' << sum << endl;
    return 0;
}


Measured memory_bytes: 3176
#include<stdio.h>
int main(void){
    int a = 0;
    int b = 0;
    int c = 0;
    scanf("%d%d%d",&a,&b,&c);
    if(a < b&&b < c){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	if(a<=8 && b<=8){
		cout << "Yay!" << endl;
	}else{
		cout << ":(" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
s = input()
wa = 0
for i in range(len(s)):
    if i%2 == 0 and (s[i] == 'R' or s[i] == 'U' or s[i] == 'D' ):
        continue
    elif i%2 == 1 and (s[i] == 'L' or s[i] == 'U' or s[i] == 'D'):
        continue
    else:
        wa += 1
if wa == 0:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
 long long int n,m,i,f,j,ans=0,x,y;
 cin>>n>>m;
 set<int>s[n+1];
 long long int h[n+1];
 for(i=1;i<=n;i++)
 {
     cin>>h[i];
 }
 for(i=1;i<m+1;i++)
 {
     cin>>x>>y;
     s[x].insert(y);
     s[y].insert(x);
 }
 for(i=1;i<=n;i++)
 {f=0;
     if(s[i].empty())
     ans++;
     else
     {
         for(auto j:s[i])
         {
             if(h[i]<=h[j])
             {
                 f=1;
                 break;
             }
         }
         if(f==0)
         ans++;
     }
 }
 cout<<ans;
 return 0;
}
 
 
   

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

int main(){
    int s,s1;
    cin >> s;
    s1=s%100;
    s/=100;

    if(s1<=12 &&s1>=1){
        if(s<=12 && s>=1){
            cout <<"AMBIGUOUS"<< endl;
        }else{
            cout <<"YYMM"<< endl;
        }

    }else{
        if(s<=12 && s>=1){
            cout << "MMYY" << endl;        
        }else{
            cout <<"NA"<< endl;
        }
    }
}

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

using namespace std;
typedef set<string> sset;
typedef set<char> cset;

int main() {
    string s;
    cin >> s;
    int k;
    cin >> k;
    sset dict;
    cset chars;
    for(auto i = s.begin(); i<s.end(); ++i) {
        chars.insert(*i);
    }
    
    for(char c : chars) {
        for(int from=0; from<s.size(); from++) {
            if(s[from]==c) {
                for(int to=s.size(); to>from; to--) {
                    string sub = s.substr(from, to-from);
                    pair<sset::iterator, bool> ins = dict.insert(sub);
                    if(!ins.second) break;
                }
            }
        }
        if(dict.size() >= k) {
            auto itr = dict.begin();
            for(int i=1; i<k; i++) ++itr;
            cout << *itr << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 992000
N = int(input().rstrip())
a = []
for i in range(N):
    a.append(int(input().rstrip()))

a.sort()
total = sum(a)

if (total % 10) == 0:
    for i in range(N):
        if (a[i] % 10) != 0:
            total = total - a[i]
            break

print(0 if (total % 10) == 0 else total)


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

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

using namespace std;

int main()
{
  ll n;
  cin >> n;
  ll sum = 0;
  for (ll i = 0; i < n; ++i) {
    sum += i;
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
typedef struct point{
    double x,y;
} P;
void show(P p)
{
    cout<<fixed<<setprecision(5);
    cout<<p.x<<' '<<p.y<<endl;
}
void work(P p1,P p2,int n)
{
    if(n==0)
        return;
    P p3,p4,p5;
    double dx,dy,a,b;
    p3.x = 2./3*p1.x+p2.x/3;
    p3.y = 2./3*p1.y+p2.y/3;
    p4.x = 1./3*p1.x+p2.x*2/3;
    p4.y = 1./3*p1.y+p2.y*2/3;
    dx = p4.x-p3.x;
    dy = p4.y-p3.y;
    a = 0.5;
    b = sqrt(3)/2;
    p5.x = p3.x+a*dx-b*dy;
    p5.y = p3.y+dx*b+a*dy;
    work(p1,p3,n-1);
    show(p3);
    work(p3,p5,n-1);
    show(p5);
    work(p5,p4,n-1);
    show(p4);
    work(p4,p2,n-1);
}
int main()
{
    int n;
    P p1,p2;
    p1.x = p1.y = 0;
    p2.x = 100;
    p2.y = 0;
    cin>>n;
    show(p1);
    work(p1,p2,n);
    show(p2);
    return 0;
}

Measured memory_bytes: 3288
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define M 998244353

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;

    while(t--)
    {
        int N;
        cin>>N;
        int sum=0;
        for(int i=1;i<=N;i++)
        {
            if(i%3==0 || i%5==0)
            {
                continue;
            }
            sum+=i;
        }
        cout<<sum;
    }

   return 0;

//    cout<<"Sum of x+y = " << z;
}


Measured memory_bytes: 3612
a,b,c,x,y = map(int, input().split())
kei = 0
if c >= a/2 + b/2:
    kei = a * x + b*y

elif c*2 <= a+ b and a >= c * 2 and x > y:
    kei += c * (min(x,y)*2)
    kei += c * ((x - y)*2)

elif c*2 <= a+ b and b >= c * 2 and x < y:
    kei += c * (min(x,y)*2)
    kei += c * ((y - x)*2)

elif c <= a/2 + b/2:
    kei += c * (min(x,y)*2)
    if x > y:
        kei += a * (x -y)
    else:
        kei += b *(y-x)


print(kei)

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

#define ll long long
#define int long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf (int)(1e18)
#define ps(x, y) fixed << setprecision(y) << x
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define all(p) p.begin(), p.end()
#define ub(a, b) upper_bound(all(a), b)
#define lb(a, b) lower_bound(all(a), b)
#define sz(x) (int)x.size()
#define PI 3.14159265
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void run()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=(int)(405);
vector<vi> dp(N,vi(N,-1));
vi a(N,0);
vi sum(N,0);
int solve(int l,int r)
{
    if(l>=r)
    {
        return 0;
    }
    int &res=dp[l][r];
    if(res!=-1)
    {
        return res;
    }
    res=inf;
    for(int i=l;i<r;i++)
    {
        res=min(res,solve(l,i)+solve(i+1,r)+sum[r]-sum[l]+a[l]);
    }
    return res;
}
void solution()
{
    int n;
    cin>>n;
    rep(i,0,n)
    {
        cin>>a[i];
    }
    sum[0]=a[0];
    for(int i=1;i<n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    int ans=solve(0,n-1);
    cout<<ans<<endl;
    return;
}
int32_t main()
{
    run();
    solution();
    return 0;
}

Measured memory_bytes: 4976
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
 

int main() {
	// 入力
	ll N;
	cin >> N;
	ll p[N];
	for (ll i = 0; i < N; ++i) cin >> p[i];
 
	// 解法
	ll value_max = 0;
	ll index_max = -1;
	REP(i,N){
		if (p[i]>value_max){
			value_max = p[i];
			index_max = i;
		} 
	}
	ll ans = 0;
	REP(i,N){
		if (i==index_max) ans += p[i]/2;
		else ans += p[i];
	}
	// cout << index_max << endl;
	cout << ans << endl;
}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
L = []
for kind, point in LIR(n):
    L += [(point, kind)]


L.sort()
que1 = deque(L[-k:])
que2 = deque(L[:-k])
ret = sum([point for point, kind in que1])
kind_cnt = Counter([i[1] for i in que1])
now_kinds = len(kind_cnt)
ans = ret + now_kinds ** 2
while que1:
    point1, kind1 = que1.popleft()
    if kind_cnt[kind1] > 1:
        kind_cnt[kind1] -= 1
        ret -= point1
        while que2:
            point2, kind2 = que2.pop()
            if not kind_cnt[kind2]:
                kind_cnt[kind2] += 1
                ret += point2
                now_kinds += 1
                ans = max(ans, ret + now_kinds ** 2)
                break
        else:
            break



print(ans)

Measured memory_bytes: 73052
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int T1, T2;
        Int A1, A2;
        Int B1, B2;
        cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;
        Int P = T1 * (B1 - A1);
        Int Q = T2 * (B2 - A2);

        if (P + Q == 0ll) {
            cout << "infinity" << endl;
            return;
        }
        if (P < 0) {
            P = -P;
            Q = -Q;
        }
        if (P + Q > 0) {
            cout << 0 << endl;
            return;
        }
//        if ((P >= 0 && Q >= 0) || (P <= 0 && Q <= 0)) {
//            cout << 0 << endl;
//            return;
//        }

        Int dec = -(P + Q);


        Int ans = (P / dec + 1) * 2 - 1ll;

        if (P % dec == 0) ans--;
        cout << ans << endl;
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


Measured memory_bytes: 888
def mod_inv(inv,a,m):
    i=a
    if inv.get(a,0)!=0:
        return inv[a]
    e=m-2
    tmp=1
    while e!=1:
        if e%2==1:
            tmp*=a
            tmp%=m
        a*=a
        a%=m
        e//=2
    a*=tmp
    a%=m
    inv[i]=a
    return a

def factrial(fact,a,m):
    for i in range(1,a+1):
        fact[i]=fact[i-1]*i%mod

def comb(fact,inv,a,b,m):
    return (fact[a+b]*mod_inv(inv,fact[a],m)*mod_inv(inv,fact[b],m))%m

H,W,A,B=list(map(int,input().split()))
mod=10**9+7
fact=[1 for _ in range(H+W+1)]
inv={}
factrial(fact,H+W,mod)

ans=0
for i in range(W-B):
    ans+=comb(fact,inv,B+i,H-A-1,mod)*comb(fact,inv,W-B-1-i,A-1,mod)
    ans%=mod
print(ans)

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

using namespace std;

int main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector <long long> ans(n);
    ans[0] = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i & 1) ans[0] -= a[i];
        else ans[0] += a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        ans[i + 1] = 2 * a[i] - ans[i];
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 2944
program main
  
  implicit none
  character(3) :: n 
  integer :: i,j
  
  read(*,*) n 
   
  j = 0 
  do i = 1, 3
    if(n(i:i) == "7") j = 1
  end do
  if(j==1) then
    print*, "Yes"
  else
    print*, "No"
  end if
end program main


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

int main() {
	string str;
	getline(cin,str);
	for(unsigned int i=0;i<str.size();++i) {
		if(str[i]>='a' && str[i]<='z') {
			str[i]+='A'-'a';
		} else if(str[i]>='A' && str[i]<='Z') {
			str[i]+='a'-'A';
		}
	}
	cout << str << endl;
	return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;
ll a[110];
int main(){
    ll n,m,ans=0,sum=0;
    cin>>n>>m;
    ll p=ceil((ld)n/m);
    ll pp=labs(n-m*p);
    cout<<min(n,pp);
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 10000000000000
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
#define repN_1(i, n) for(ll i = 0; i < (ll)(n - 1); i++)
#define repM(i, n) for(ll i = (ll)(n - 1); i >= 0; i--)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

int main()
{
	cout << fixed << setprecision(18);
	ll x;
	ll ans = 0;
	ll m = 100;

	cin >> x;

	while (1)
	{
		m = (ll)floor(m * 1.01);
		ans++;
		if (m >= x)
			break;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3744