akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define MOD 1000000007 
#define INF 1000000000000000000
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing

int main() {
	int n, k;
	cin >> n >> k;
	vector <int> v1, v2;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(x < 0)
			v1.push_back(-x);
		else
			v2.push_back(x);
	}
	reverse(all(v1));
	int n1 = (int) v1.size(), n2 = (int) v2.size();
	int ans = MOD;
	if(n1 >= k)
		ans = min(ans, v1[k - 1]);
	if(n2 >= k)
		ans = min(ans, v2[k - 1]);
	for (int i = 0; i < min(k - 1, n2); i++) {
		if(k - i - 1 <= n1) {
			ans = min(ans, v2[i] + v1[k - i - 2] + min(v2[i], v1[k - i - 2]));
		}
	}
	cout << ans;
}


Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int l,r;
    cin>>l>>r;
    double a[l][r];
    for(int i=0;i<l;i++){
            for(int j=0;j<r;j++){
        cin>>a[i][j];
      }
    }
    double d;
    long long int e=0,ans=0;
    for(int i=0;i<l;i++){
        for (int j=i+1;j<l;j++){
                d=0;
            if (i!=j){
                for(int k=0;k<r;k++){
                    d+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
                }
        d=sqrt(d);
        e=d;
        if(e==d){
            ans++;
        }
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import re

a = input()

if re.match('^([a-zA-Z]*?)keyence$', a):
  print("YES")
else:
  if re.match('^k([a-zA-Z]*?)eyence$', a):
    print("YES")
  else:
    if re.match('^ke([a-zA-Z]*?)yence$', a):
      print("YES")
    else:
      if re.match('^key([a-zA-Z]*?)ence$', a):
        print("YES")
      else:
        if re.match('^keye([a-zA-Z]*?)nce$', a):
          print("YES")
        else:
          if re.match('^keyen([a-zA-Z]*?)ce$', a):
            print("YES")
          else:
            if re.match('^keyenc([a-zA-Z]*?)e$', a):
              print("YES")
            else:
              if re.match('^keyence([a-zA-Z]*?)$', a):
                print("YES")
              else:
                print("NO")



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

int main(){
    int n;
    cin >> n;
    int cur = 0;
    bool ok = false;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        if(a == b){
            cur ++;
        }
        else{
            cur = 0;
        }

        if(cur == 3){
            ok = true;
        }
    }

    if(ok){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

#define ll long long
#define ull unsigned long long
#define met(a,x) memset(a,x,sizeof(a))
#define inf 0x3f3f3f3f
#define mp make_pair;

using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
ll a[N];
ll dp[N];
ll b[N];
bool cmp(ll a,ll b){
    return a>b;
}
priority_queue<ll> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    met(b,0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>a[i];
       q.push((-a[i]));
    }
    int ans=1;
    ll x,y;
    while(q.size()>1){
        x=abs(q.top());
        q.pop();
        y=abs(q.top());
        q.pop();
        if((2*x>=y||x>=y)&&(2*y>=x||y>=x)){
            ans++;
        }
        else{
            ans=1;
        }
        q.push(-(x+y));
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2804
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
n = int(input())

for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      ans += gcd(i, j, k)
      
print(ans)

Measured memory_bytes: 69568
def main():
  k = int(input())
  num = 7 % k
  first = num
  ans = 1
  while num != 0:
    ans += 1
    num = (num*10 + 7)%k
    if num == first or ans > 2000000:
      ans = -1
      break
  print(ans)
    
    
if __name__ == "__main__":
  main()

Measured memory_bytes: 9168
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		int sum = 0;
		for (int c : coin)
			sum += c * scanner.nextInt();
		System.out.println(sum >= 1000 ? 1 : 0);
	}

	int[] coin = { 1, 5, 10, 50, 100, 500 };
}

Measured memory_bytes: 17340
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

res = 0
for i in range(N):
    kill = B[i]
    if A[i]>=kill:
        res += kill
        A[i] -= kill
    else:
        res += A[i]
        kill -= A[i]
        A[i] = 0
        res += min(A[i+1],kill)
        A[i+1] = max(0,A[i+1]-kill)
print(res)

Measured memory_bytes: 82020
n,k = map(int,input().split())
A = list(map(int,input().split()))
P = [0]+A
for i in range(1,n+1):
    P[i] += P[i-1]
temp = []
for i in range(n+1):
    for j in range(i+1, n+1):
        temp.append(P[j]-P[i])
ans = 0
for i in range(40, -1, -1):
    cur = ans+2**i
    cnt = 0
    for j in range(len(temp)):
        if temp[j]&cur == cur:
            cnt += 1
        if cnt >= k:
            break
    if cnt == k:
        ans += 2**i
print(ans)


Measured memory_bytes: 65916
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

output:
1
2
"""

import sys
from math import ceil, log2, isinf


class SegmentTree(object):
    __slots__ = ('dat', 'tree_range')

    def __init__(self):
        """
        Init a SegmentTree with update and find for RMQ.
        """
        self.tree_range = end
        self.dat = [float('inf')] * (2 * self.tree_range - 1)

    # let A[k]=a
    def update(self, k, a):
        k += self.tree_range - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    # get min(A[s] A[s+1] ... A[t])
    def find(self, s, t, k=0, l=0, r=0):
        if r <= s or t <= l:
            return float('inf')

        if s <= l and r <= t:
            return self.dat[k]
        else:
            vl = self.find(s, t, k * 2 + 1, l, (l + r) // 2)
            vr = self.find(s, t, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def action(cmd_list):
    for query in cmd_list:
        cmd, ele_1, ele_2 = map(int, query)
        if cmd == 0:
            case.update(ele_1, ele_2)
        elif cmd == 1:
            res = case.find(s=ele_1, t=ele_2 + 1, r=end)
            if isinf(res):
                print(INIT_MAX)
            else:
                print(res)

    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n_num, q_num = map(int, _input[0].split())
    q_list = map(lambda x: x.split(), _input[1:])

    end = pow(2, ceil(log2(n_num)))
    INIT_MAX = pow(2, 31) - 1

    case = SegmentTree()

    ans = action(q_list)

Measured memory_bytes: 19708
a,b,c,x,y=map(int,input().split())
if max(x,y)==x:
  large=a
  small=b
else:
  large=b
  small=a
kingaku=0
if a+b>=2*c:
  kingaku+=2*c*min(x,y)
  if large>=2*c:
    kingaku+=2*c*(max(x,y)-min(x,y))
  else:
    kingaku+=large*(max(x,y)-min(x,y))
else:
  kingaku+=a*x+b*y

print(kingaku)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
char a[10],b[10],c[10];
cin >> a >> b  >> c;
a[0] -= 32;
b[0] -= 32;
c[0] -= 32;
cout << a[0] << b[0] << c[0] << endl;
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
//BIAR MANTAB LAH YA
#define Willy using
#define Indrayana namespace
#define Komara std
 
Willy Indrayana Komara;
 
using ll = long long int;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  	ll a;
    double b;
    cin >> a >> b;
    //cout << (ll)round(b*100) << endl;
  	cout << a*(ll)round(b*100)/100 << '\n';
}

Measured memory_bytes: 3732
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
    public static void main(String[] args)throws IOException {
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        String[] s1 = bufferedReader.readLine().split(" ");
        String[] s2 = bufferedReader.readLine().split(" ");
        long p1=-1,p2=-1;
        boolean one=false,two=false,three=false;
        if(Long.parseLong(s[0])==Long.parseLong(s1[0]))
        {
            p1 = Long.parseLong(s[1]);
            p2 = Long.parseLong(s1[1]);
            one=true;
            two=true;
        }
        else if(Long.parseLong(s[0]) == Long.parseLong(s1[1]))
        {
            p1 = Long.parseLong(s[1]);
            p2 = Long.parseLong(s1[0]);
            one=true;
            two=true;
        }
        else if(Long.parseLong(s[0])==Long.parseLong(s2[0]))
        {
            p1 = Long.parseLong(s[1]);
            p2= Long.parseLong(s2[1]);
            one=true;
            three=true;
        }
        else if(Long.parseLong(s[0])==Long.parseLong(s2[1]))
        {
            p1=Long.parseLong(s[1]);
            p2 = Long.parseLong(s2[0]);
            one=true;
            three=true;
        }
        else if(Long.parseLong(s[1])==Long.parseLong(s1[0]))
        {
            p1 = Long.parseLong(s[0]);
            p2 = Long.parseLong(s1[1]);
            one=true;
            two=true;
        }
        else if(Long.parseLong(s[1]) == Long.parseLong(s1[1]))
        {
            p1 = Long.parseLong(s[0]);
            p2 = Long.parseLong(s1[0]);
            one=true;
            two=true;
        }
        else if(Long.parseLong(s[1])==Long.parseLong(s2[0]))
        {
            p1 = Long.parseLong(s[0]);
            p2= Long.parseLong(s2[1]);
            one=true;
            three=true;
        }
        else if(Long.parseLong(s[1])==Long.parseLong(s2[1]))
        {
            p1=Long.parseLong(s[0]);
            p2 = Long.parseLong(s2[0]);
            one=true;
            three=true;
        }
        boolean ans=false;
        if(two==false)
        {
            if(p1==Long.parseLong(s1[0])||p1==Long.parseLong(s1[1]))
            {
                ans=true;
            }
            else if(p2==Long.parseLong(s1[0])||p2==Long.parseLong(s1[1]))
            {
                ans=true;
            }
        }
        else if(three==false)
        {
            if(p1==Long.parseLong(s2[0])||p1==Long.parseLong(s2[1]))
            {
                ans=true;
            }
            else if(p2==Long.parseLong(s2[0])||p2==Long.parseLong(s2[1]))
            {
                ans=true;
            }
        }
        if(p1>-1&&p2>-1&&ans==true)
        {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 22484
#include<stdio.h>
int main(void){
 int N;
  int K;
  scanf("%d",&N);
  scanf("%d",&K);
  int A = K;
  //int a;
  
  for(int i = 0 ;i<N-1;i++){    
    A*=(K-1);//= A = A * (k-1)
  }
  printf("%d",A);
  
}

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

int main()
{
	int n;
	cin >> n;
	bool check(int x);
	
	if(check(n))
	    cout << "Yes";
	else if(!check(n))
	    cout << "No";
} 
bool check(int x)
{
	int a[4],f=0;
	
	a[3] = x%10;
	x/=10;
	a[2] = x%10;
	x/=10;
	a[1] = x;
	
	for(int i=1;i<=3;i++)
	{
		if(a[i]==7)
			f++;
	}
	
	if(f>=1)
	    return true;
	else
	    return false;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector<long long> list(1);
    long long n, k, current;
    cin >> n >> k;
    cin >> list[0];
    for (long long i = 1; i < n; i++) {
        cin >> current;
        list.emplace_back(current);
    }
    sort(list.begin(), list.end());
    long long sum = 0;
    list.resize(k);
    list.shrink_to_fit();
    for (auto x : list) {
        sum += x;
    }
    cout << sum << '\n';
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define N 2010
using namespace std;
int n, k, q;
int a[N];

int tree[N];
int size;
#define lowbit(x) (x) & (-x)
inline void Add(int x, int t)
{
	while(x <= size)
	{
		tree[x] += t;
		x += lowbit(x);
	}
}
inline int Query(int x)
{
	int Ans = 0;
	while(x > 0)
	{
		Ans += tree[x];
		x -= lowbit(x);
	}
	return Ans;
}
struct D{
	int x, p;
}B[N];
inline bool cmp(D x, D y)
{
	return x.x < y.x;
}
int x[N];
int y[N];
int main()
{
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1; i <= n; ++ i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++ i)
		B[i].x = a[i], B[i].p = i;
	sort(B + 1, B + n + 1, cmp);
	int Ans = 2147483647;
	for(int i = 0; i <= n; ++ i)
	{
		memset(tree, 0, sizeof(tree));
		size = n;
		x[0] = -1;
		for(int j = 1; j <= n; ++ j)
			if(a[j] <= B[i].x)
				x[j] = -1;
			else
				x[j] = x[j - 1] + 1;
		y[n + 1] = -1;
		for(int j = n; j >= 1; -- j)
			if(a[j] <= B[i].x)
				y[j] = -1;
			else
				y[j] = y[j + 1] + 1;
		for(int j = 1; j <= n; ++ j)
		{
			Add(j, x[j] + y[j] + 1);
			Add(j + 1, - x[j] - y[j] - 1);
		}
		int tot = 0;
		int Min = 2147483647;
		int Max = 0;
		for(int j = i + 1; j <= n; ++ j)
		{
			if(Query(B[j].p) >= k)
			{
				++ tot;
				Add(B[j].p - x[B[j].p], -1);
				Add(B[j].p + y[B[j].p] + 1, 1);
				Min = min(B[j].x, Min);
				Max = max(B[j].x, Max);
			}
			if(tot == q)
				break;
			
		}
		if(tot != q)
			break;
		else
			Ans = min(Ans, Max - Min);
	}
	printf("%d", Ans);
	return 0;
}

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

using namespace std;

int N;
int M;
vector<int> V;
int X[100005];

int main(void) {

	cin >> N >> M;

	for (int i = 1; i <= M; i++) {
		cin >> X[i];
		V.push_back(X[i]);
	}

	sort(V.begin(), V.end());

	int C = 1;
	vector<long long int > W;

	for (int i = 1; i < (int)V.size(); i++) {
		if (V[i] == V[i - 1] + 1) {}
		else { C++; W.push_back(V[i] - V[i - 1] - 1); }
	}

	long long int ans = 0;

	ans += M - N;
	sort(W.begin(), W.end());

	for (int i = 0; i < C - N; i++) {
		ans += W[i];
	}

	if (N >= M) { ans = 0; }


	cout << ans << endl;

	//system("pause");
	return 0;
}

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

int main()
{
	int alph[26] = {};
	char a[50];
	scanf("%s", &a, 50);
	for (int i = 0; a[i] != '\0';i++)
	{
		"%d\n",alph[a[i] - 'a']++;
		if (alph[a[i] - 'a'] > 1)
		{
			printf("%s\n", "no");
			return 0;
		}
	}
	printf("%s\n", "yes");
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W;
    cin >> H >> W;
    vector<vector<int>> dist(10,vector<int>(10,0));
    for (int i=0;i<10;i++){
        for (int j=0;j<10;j++){
            cin >> dist[i][j];
        }
    }
    for (int k=0;k<10;k++){
        for (int i=0;i<10;i++){
            for (int j=0;j<10;j++){
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    int sum = 0;
    for (int i=0;i<H;i++){
        for (int j=0;j<W;j++){
            int a;
            cin >> a;
            if (a==-1) continue;
            if (a==1) continue;
            sum += dist[a][1];
        }
    }
    cout << sum << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#define INF 100000000
#define _INF -100000000
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> P;

struct node {
	bool done;
	vi ed, dist;
	int id, from;
	ll d;
	bool operator<(const node & another) const {
		return !(d != another.d ? d < another.d : id < another.id);
	}
};


void dijkstra(vector<node> nodes, int n, int start) {
	priority_queue<node> pq;
	nodes[start].d = 0;
	pq.push(nodes[start]);
	while (pq.size()) {
		node focus = pq.top(); pq.pop();
		if (nodes[focus.id].done) continue;
		Loop(i, focus.ed.size()) {
			if (focus.d + focus.dist[i] < nodes[focus.ed[i]].d) {
				nodes[focus.ed[i]].d = focus.d + focus.dist[i];
				nodes[focus.ed[i]].from = focus.id;
				pq.push(nodes[focus.ed[i]]);
			}
		}
		nodes[focus.id].done = true;
	}
	Loop(i, n) {
		if (nodes[i].d == INFLL) cout << "INF" << endl;
		else {
			cout << nodes[i].d;
			/*
			stack<int> stk;
			node focus = nodes[i];
			stk.push(i);
			while (focus.from != -1) {
			stk.push(focus.from);
			focus = nodes[focus.from];
			}
			while (stk.size()) {
			cout << " " << stk.top();
			stk.pop();
			}
			*/
			cout << endl;
		}
	}
	return;
}

int main() {
	int v, e, r; cin >> v >> e >> r;
	vector<node> nodes(v + 5);
	Loop(i, v) nodes[i] = { false,{},{}, i, -1, INFLL };
	Loop(i, e) {
		int s, t, d; cin >> s >> t >> d;
		nodes[s].ed.push_back(t);
		nodes[s].dist.push_back(d);
		/*
		nodes[t].ed.push_back(s);
		nodes[t].dist.push_back(d);
		*/
	}
	dijkstra(nodes, v, r);
}

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

ll mod = 1e9+7;

ll add(ll a, ll b){
    return (a%mod + b%mod)%mod;
}

int main(){
    string ABC = "ABC";

    string S;  cin >> S;
    int N = S.length();

    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(N+1, vector<ll>(4,0));
    dp[0][0] = 1;
    for(int i=0; i<N; i++){
        ll m1 = (S[i]=='?' ? 3:1);
        dp[i+1][0] = (m1*dp[i][0])%mod;
        for(int j=1; j<=3; j++){
            ll m2 = ((S[i]==ABC[j-1] || S[i]=='?') ? 1:0);
            dp[i+1][j] = add(m1*dp[i][j], m2*dp[i][j-1]);
        }
    }
    cout << dp[N][3] << endl;
}


Measured memory_bytes: 7424
#include<iostream>

using namespace std;
void swap(int i, int j, int k[]) {
	int temp = k[i];
	k[i] = k[j];
	k[j] = temp;
}
int main() {
	int n;
	cin >> n;
	int ii[100000] = {};
	int p[100000] = {};
	for (int i = 0; i < n; i++) {
		ii[i] = i + 1;
		cin >> p[i];
	}
	int x = 0;
	for (int i = 0; i < n; ++i) {
		if ((p[i] == ii[i])&&(i < n-1)) {
			swap(i, i + 1, p);
			x++;
		}
		else if (p[i] == ii[i]) {
			swap(i, i + 1, p);
			x++;
		}
	}
	cout <<x << endl;

	return 0;
}


Measured memory_bytes: 1152
#include<iostream>
#include<cstring>
#include<climits>
#include<cmath>
#include<algorithm>

using namespace std;
#define lli long long int
#define mod 1000000007

int main()
{
    lli n,k,i,t,s;
    cin>>n>>k;
    t=1;
    s=0;

    for(i=k;i<=n+1;i++)
    {
        t = ((i*(2*n-i+1)/2)%mod - (i*(i-1)/2)%mod + 1)%mod;
        // cout<<t<<endl;
        s = (s+t)%mod;
    }
    if(s<0) s+=mod;
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3632
use std::io;
const MAX_N: usize = 100000;

fn main() {
    get_line();
    let ns: Vec<u64> = read_ints();
    println!("{}", together(&ns));
}
fn together(nums: &[u64]) -> usize {
    let mut counter: Vec<usize> = vec![0;MAX_N+2];
    for &n in nums {
        counter[n as usize] += 1;
        counter[n as usize + 1] += 1;
        counter[n as usize + 2] += 1;
    }
    *counter.iter().max().expect("no such thing!")
}

fn read_ints() -> Vec<u64> {
    get_line()
        .trim()
        .split_whitespace()
        .map(|n| n.parse().unwrap())
        .collect()
}

fn get_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

Measured memory_bytes: 6396
n,m = map(int,input().split())
drink = [list(map(int,input().split())) for _ in range(n)]
s_drink = sorted(drink,key=lambda x:x[0])
ans = 0
count = 0
for i in range(n):
  if s_drink[i][1] + count > m:
    ans += s_drink[i][0] * (m - count)
    count += (m - count)
    break
  else:
    ans += s_drink[i][0] * s_drink[i][1]
    count += s_drink[i][1]
print(ans)

Measured memory_bytes: 29796
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n; cin>>n;
    if (n >= 30) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3664
n = int(input())
s = input()
l = len(s)
mincnt = n
nums = [[0, 0]]
if s[0] == ".":
    nums[0][0] = 1
else:
    nums[0][1] = 1
if l == 1:
    print(0)
    exit()

for c in s[1:]:
    last = nums[-1]
    nums.append([last[0] + 1, last[1]] if c == "." else [last[0], last[1] + 1])

for i in range(0, l):
    b_before = nums[i][1] - (1 if s[i] == "#" else 0)
    w_after = nums[-1][0] - nums[i][0] + (1 if s[i] == "." else 0)
    mincnt = min(mincnt, b_before + w_after)
mincnt = min(mincnt, nums[-1][1])
print(mincnt)

Measured memory_bytes: 30184
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef pair<pl, ll> ppl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

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

  ll l=0, r=n-1;
  while(r-l>=3) {
    ll m = (l+r)/2, gl=0, gr=0;
    rep2(i, l, m) gl = __gcd(gl, a[i]);
    rep2(i, m+1, r) gr = __gcd(gr, a[i]);
    if(gl > gr) l=m+1;
    else r=m;
  }

  ll g1=0, g2=0, g3=0;
  rep(i, n) {
    if(i != l) g1 = __gcd(g1, a[i]);
    if(i != l+1) g2 = __gcd(g2, a[i]);
    if(i != l+2) g3 = __gcd(g3, a[i]);
  }
  cout << max(max(g1, g2), g3) << newl;
  return 0;
}

Measured memory_bytes: 3920
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

 void bubbleSort(int a[], int n){
    int flag=1;
    int cnt=0;
    while(flag==1){
        flag=0;
        for(int i=n-1; i>0; i--){
            if(a[i]<a[i-1]){
                cnt++;
                swap(a[i],a[i-1]);
                flag=1;
            }
        }
    }
    for(int i=0; i<n; i++){
        cout<<a[i];
        if(i!=n-1) cout<<" ";
    }
    cout<<endl;
    cout<<cnt<<endl;
}

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    bubbleSort(a,n);
    return 0;
}


Measured memory_bytes: 3100
using System;

public class Po
{
    public int x { get; set; }
    public int y { get; set; }
    public bool second { get; set; }
}

public class Hello
{
    public static void Main()
    {
        var map = new bool[9, 5];
        for (int i = 0; i < 9; i++)
        {
            var s = Console.ReadLine().Trim();
            var jmax = i % 2 == 0 ? 4 : 5;
            for (int j = 0; j < jmax; j++)
                if (s[j] == '1') map[i, j] = true;
        }
        var p = new Po { x = 0, y = 0 };
        poRight(map, p);
        Console.WriteLine();
    }
    public static void poRight(bool[,] map, Po p)
    {
        if (p.x == 0 && p.y == 0)
            if (p.second) return;
            else p.second = true;
        var nx = p.x; var ny = p.y;
        if (map[nx, ny]) Console.Write("R");
        if (nx - 1 >= 0 && ny + 1 < 5 && map[nx - 1, ny + 1]) { p.x--; p.y++; poUp(map, p); }  
        else if (ny + 1 < 5 && map[nx, ny + 1]) { p.y++; poRight(map, p); }
        else if (nx + 1 < 9 && ny + 1 < 5 && map[nx + 1, ny + 1]) { p.x++; p.y++; poDown(map, p); }
        else { poLeft(map, p); }
    }
    public static void poDown(bool[,] map, Po p)
    {
        var nx = p.x; var ny = p.y;
        if (map[nx, ny]) Console.Write("D");
        if (nx + 1 < 9 && map[nx + 1, ny]) { p.x++; poRight(map, p); }
        else if (nx + 2 < 9 && map[nx + 2, ny]) { p.x += 2; poDown(map, p); }
        else if (nx + 1 < 9 && ny - 1 >= 0 && map[nx + 1, ny - 1]) { p.x++; p.y--; poLeft(map, p); } 
        else { poUp(map, p); }
    }
    public static void poUp(bool[,] map, Po p)
    {
        var nx = p.x; var ny = p.y;
        if (map[nx, ny]) Console.Write("U");
        if (nx - 1 >= 0 && ny - 1 >= 0 && map[nx - 1, ny - 1]) { p.x--; p.y--; poLeft(map, p); } 
        else if (nx - 2 >= 0 && map[nx - 2, ny]) { p.x -= 2; poUp(map, p); }
        else if (nx - 1 >= 0  && map[nx - 1, ny ]) { p.x--; poRight(map, p); } 
        else { poDown(map, p); }
    }
    public static void poLeft(bool[,] map, Po p)
    {
        var nx = p.x; var ny = p.y;
        if (map[nx, ny]) Console.Write("L");
        if (nx + 1  < 9  && map[nx + 1, ny ]) { p.x++; poDown(map, p); }
        else if (ny - 1 >= 0 && map[nx, ny - 1]) { p.y--; poLeft(map, p); }
        else if (nx - 1 >= 0 && map[nx - 1, ny ]) { p.x--; poUp(map, p); }
        else { poRight(map, p); }
    }
}

Measured memory_bytes: 8816
n,m = map(int,input().split())
dic = {}
for _ in range(m):
    a,b = map(int,input().split())
    if not a in dic.keys():
        dic[a] = [b]
    else:
        dic[a].append(b)
for i in dic[1]:
    if i in dic.keys() and n in dic[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

const ll INF = 1ll<<60;

typedef pair<ll,ll> P;

int main() {
  ll n, x, d;
  cin >> n >> x >> d;

  if (d == 0) {
    if (x == 0) {
      cout << 1 << endl;
    } else {
      cout << n+1 << endl;
    }
    return 0;
  }

  map<int,vector<P>> mp;
  rep(i,n+1) {
    ll s = x*i;
    ll l = (ll)i*(i-1)/2;
    ll r = l + (ll)i*(n-i);
    s += l*d;
    r -= l;
    mp[(s+(d<<30))%d].emplace_back(s,r);
  }

  ll ans = 0;
  for (auto p : mp) {
    auto a = p.second;
    int m = a.size();
    rep(i,m) a[i].first = (a[i].first-p.first)/d;
    vector<P> ev;
    rep(i,m) {
      ev.emplace_back(a[i].first, 1);
      ev.emplace_back(a[i].first+a[i].second+1, -1);
    }
    sort(ev.begin(), ev.end());
    ll cnt = 0, pre = -INF;
    for (auto e : ev) {
      ll len = e.first-pre;
      if (cnt) ans += len;
      cnt += e.second;
      pre = e.first;
    }
  }
  cout << ans << endl;
  return 0;
}


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

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

  vector<int> D(N); // N個の数学の点数データ
  int height = 0;
    
  // 数学の点数データを受け取る
  for (int i = 0; i < N; i++) {
    cin >> D.at(i);
  }

  for (int i = 0; i < 101; i++) {
    for (int j = 0; j < N; j++) {
      if (D.at(j) == i) {
        height++;
        break;
      }
    }
  }
  
  cout << height << endl;
}


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

char s[1000010];
int sum[1000010][2];
int n, m;

long long solve(int k){
	int l = 1, r = k;
	long long tot = 0;
	for (int i = 1; i <= k; i++){
		tot += (s[i] == 'C' ? sum[i][0] : 0);
	}
	long long ans = 0;
	for (int i = 1; i <= n; i++){
		if (s[i] == 'D') ans += tot;
		if (s[i] == 'M') tot -= sum[min(i + k - 1, n)][1] - sum[i - 1][1];
		if (i + k <= n && s[i + k] == 'C') tot += sum[i + k][0] - sum[i][0];
	}
	return ans;
}

int main(){
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++){
		sum[i][0] = sum[i - 1][0] + (s[i] == 'M');
		sum[i][1] = sum[i - 1][1] + (s[i] == 'C');
	}
	int m; scanf("%d", &m);
	for (int i = 0; i < m; i++){
		int k; scanf("%d", &k);
		printf("%lld\n", solve(k));
	}
	return 0;
}


Measured memory_bytes: 9088
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 3005;
int a[maxN];
vector < int > g[maxN];
int n;
bool win[maxN];
void solve(int v, int p) {
    win[v] = false;
    for (int to : g[v]) {
        if (to == p) continue;
        solve(to, v);
        if (a[v] > a[to]) win[v] |= !win[to];
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    for (int i = 1; i <= n; i++) {
        solve(i, -1);
        if (win[i]) cout << i << " ";
    }
    return 0;
}

Measured memory_bytes: 4068
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define RREP(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

bool ok(int i, int n){
  int tmp = i;
  int l[10]={};
  while(tmp>0){
    int tmp2 = tmp % 10;
    tmp /= 10;
    if(l[tmp2] != 0) return false;
    else l[tmp2]++; 
  }
  REP(j,10){
    if(j>=1 && j <= n && l[j] != 1) return false;
    if(j==0 || j >n){
      if(l[j]!=0) return false;
    }
  }
  return true;
}
int fac(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  double ans = 0;
  cin >> N;
  vector<int> x(N),y(N);
  REP(i,N){
    cin >> x[i] >> y[i];
  }
  //double a = (double)sqrt( (x[2]-x[1])*(x[2]-x[1]) + (y[2]-y[1])*(y[2]-y[1]) );
  //cout << a;
  double d[N][N];
  REP(i,N)REP2(j,i+1,N){
    d[i][j] = (double)sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
    d[j][i] = (double)sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
    //cout << i << j << d[i][j] << endl;
  }
  REP(i,87654322){
    int tmp = i;
    if(ok(tmp,N)){
     // cout << tmp << endl;
      int tmp2 = i;
      int city[10];
      REP(j,N){
        city[j] = tmp2 % 10;
        tmp2 /= 10;
      }
      REP(j,N-1){
        ans += d[city[j]-1][city[j+1]-1];
      }
    }
  }
  ans /= fac(N);
  cout << setprecision(8) << ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    vector<ll>a(5);
    rep(i,5){
        cin>>a[i];
    }
    
    ll k;
    cin>>k;
    

    if(a[4]-a[0]>k){
        cout<<":("<<endl;
    }else{
        cout << "Yay!" << endl;
    }

    
    


    return 0;
    

}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    int total = 0;

    cin >> N;

    int s[N];
    for (int i = 0; i < N; i++) {
        cin >> s[i];
        total += s[i];
    }

    if (total%10 == 0) {
        int min = 101;
        for (int i = 0; i < N; i++) {
            if (s[i]%10 != 0) {
                min = (s[i] < min)?s[i]:min;
            }
        }

        if (min <= 100) {
            cout << (total-min) << endl;
        } else {
            cout << "0" << endl;
        }
    } else {
        cout << total << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



string S, T;
int f[26][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;
    int N = S.length();

    rep(i, 0, N) {
        int a = S[i] - 'a';
        int b = T[i] - 'a';

        f[a][b] = 1;
    }

    rep(i, 0, 26) {
        int cn = 0;
        rep(j, 0, 26) if (f[i][j]) cn++;
        if (2 <= cn) {
            printf("No\n");
            return;
        }
    }
    rep(j, 0, 26) {
        int cn = 0;
        rep(i, 0, 26) if (f[i][j]) cn++;
        if (2 <= cn) {
            printf("No\n");
            return;
        }
    }

    printf("Yes\n");
}

Measured memory_bytes: 916
#include <stdio.h>

int main() {
	int a = 0;
	int b = 0;
	int d, r;
	double f;
	scanf("%d%d", &a, &b);
	d = a / b;
	r = a % b;
	f = (double)a / b;
	printf("%d %d %f\n", d, r, f);
	return 0;
}

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

const int N = 2e5 + 10, mod = 1e9 + 7;

int n, k, arr[N];

int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1; 
    //scanf("%d", &tc);
    while(tc--) {
        scanf("%d%d", &k, &n);
        int ans = 0, mx = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &arr[i]);
            ans += arr[i] - arr[i - 1];
            mx = max(mx, arr[i] - arr[i - 1]);
        }
        ans += k - arr[n];
        mx = max(mx, arr[1] + k - arr[n]);
        printf("%d\n", ans - mx);
    }    
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> mochi(N);
  for(int i = 0; i < N; i++){
    cin >> mochi.at(i);
  }
  sort(mochi.begin(), mochi.end());
  int cnt = 1;
  for (int i = 1; i < N; i++) {
    if (mochi.at(i) != mochi.at(i-1)) {
      cnt++;
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
using System;
class main
{
    static void Main(string[] args)
    {
        while (true)
        {
            string s = Console.ReadLine();

            if (s != null)
            {
                string[] t = s.Split(' ');
                double[] u = new double[6];

                for (int i = 0; i < t.Length; ++i)
                {
                    u[i] = double.Parse(t[i]);
                }

                double y = ((u[2] * u[3]) - (u[5] * u[0])) / ((u[1] * u[3]) - (u[4] * u[0]));
                double x = (u[2] - (y * u[1])) / u[0];

                //y = ToHalfAdjust(y, 3);
                //x = ToHalfAdjust(x, 3);

                Console.WriteLine(string.Format("{0:F3} {1:F3}", x, y));
            }
            if (s == null)
            {
                break;
            }
            //Console.ReadKey();
        }
    }

    /*public static double ToHalfAdjust(double dValue, int iDigits)
    {
        double dCoef = System.Math.Pow(10, iDigits);

        return dValue > 0 ? System.Math.Floor((dValue * dCoef) + 0.5) / dCoef :
                            System.Math.Ceiling((dValue * dCoef) - 0.5) / dCoef;
    }*/
}

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

int main() {
  string s;
  cin >> s;
  if (s.size() == 2) {
    cout << s << '\n';
  } else {
    for (int i = 2; i >= 0; --i) cout << s[i];
    cout << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder rect = new StringBuilder();
		while (true) { 
			int H = sc.nextInt();
			int W = sc.nextInt();
			if (H == 0 && W == 0)
				break;
			for (int i = 0; i < H; ++i) {
				for (int j = 0; j < W; ++j) {
					rect.append("#");
				}
				rect.append("\n");
			}
			rect.append("\n");
		}
		System.out.print(rect.toString());
	}
}


Measured memory_bytes: 27856
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
#define mod 1000000007
signed main(){
    int n;
    cin>>n;
    int a[1145140];
    int sum=0;
    int ans=1000000000000000001;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int s=0;
    for(int i=0;i<n-1;i++){
        s+=a[i];
        ans=min(ans,abs(s-(sum-s)));
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3584
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(i=1;i<=n;i++)
using namespace std;
int main()
{
	ll n,K,i;
	cin>>n>>K;
	ll p[n+10],c[n+10];
	p[0]=c[0]=0;
	fr(i,n) cin>>p[i];
	fr(i,n) cin>>c[i];
	ll m=-(1LL<<55),M=-(1LL<<55);
	fr(i,n){
		ll x=i,k=K;
		vector<ll>v;
		ll sum=0,rnd=0;
		while(1){
			sum+=c[x];
			m=max(m,sum);
			v.push_back(c[x]);
			x=p[x];
			rnd++;
			if(x==i || rnd==k) break;
		}
		k-=rnd; /*cout<<rnd<<'\n';
		for(auto it:v) cout<<it<<' ';cout<<'\n';*/
		if(k!=0){
			ll z=k/rnd;
			if(z!=0)
			sum+=(sum*(z-1)),
			k-=(rnd*(z-1));
			else k=k%rnd;
			m=max(m,sum);
			for(int j=0;j<k;j++){
				sum+=v[j%rnd];
				m=max(m,sum);
			}
		}
		M=max(m,M);
		//cout<<M<<' '<<m<<'\n';
		m=-(1LL<<55);
	}
	cout<<M<<"\n";
}

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

const int M=3005;
char s[M],t[M];
int dp[M][M];
int pre[M][M];

char ans[M];

int main()
{
	scanf("%s%s",s+1,t+1);
	int n=strlen(s+1),m=strlen(t+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(dp[i][j-1]<=dp[i-1][j])
			{
				dp[i][j]=dp[i-1][j];
				pre[i][j]=0;
			}
			else
			{
				dp[i][j]=dp[i][j-1];
				pre[i][j]=1;
			}
			if(s[i]==t[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				pre[i][j]=2;
			}
		}
	}
	int l=dp[n][m],x=n,y=m;
	ans[l--]='\0';
	while(x&&y)
	{
		if(pre[x][y]==2)
		{
			ans[l--]=s[x];
			x--;
			y--;
		}
		else if(pre[x][y]==1)
		{
			y--;
		}
		else
			x--;
	}
	printf("%s\n",ans);
	return 0;
}

Measured memory_bytes: 70784
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using lli = long long int;
using ld = long double;
using pa = pair<int,int>;
using ppa = pair<pa,int>;
#define SORT(v, n) sort(v, v+n);
#define ALL(v) v.begin(),v.end()
#define VSORT(v) sort(ALL(v))
#define GRESORT(v) sort(ALL(v),greater<ll>())
#define REVERSE(v) reverse(ALL(v))
#define overlap(v) v.erase(unique(ALL(v)),v.end())
#define debug(x) cout << #x << ": " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i = (b-1); i >= a; i--)
#define rrep(i,n) RFOR(i,0,n)
#define INF 999999999
#define mins(a,b) a = min(a,b)
#define maxs(a,b) a = max(a,b)

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

//8近傍
//int dy[]={0,0,1,-1,1,1,-1,-1};
//int dx[]={1,-1,0,0,1,-1,1,-1};

ll MOD = 1000000007;

void solve() {
    int n,m; cin >> n >> m;
    vector<int> x(n),y(n,1);
    x[0] = 1; y[0] = 0;

    rep(i,m){
        int tmp,temp;
        cin >> tmp >> temp;
        tmp--; temp--;
        if(x[tmp] == 0 && y[tmp] == 0) continue;
        else if(y[tmp] == 0){
            x[tmp]--;
            x[temp]++;
        }else if(x[tmp] > 0 && y[tmp] > 0){
            y[tmp]--;
            x[temp]++;
        }else{
            y[tmp]--;
            y[temp]++;
        }
        //cout << tmp << " " << temp << endl;
        //rep(i,n) cout << "x[i] = " << x[i] << " y[i] = " << y[i] << endl;
        //cout << endl;
    }
    int cnt = 0;
    rep(i,n) cnt += (x[i] ? 1 : 0);
    cout << cnt << endl;
}

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

    solve();

    return 0;
}

Measured memory_bytes: 1024
import itertools

MOD = 10 ** 9 + 7

N, K = map(int, input().split())
a_list = list(map(int, input().split()))

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if a_list[i] > a_list[j]:
            ans += K

counts = [0] * 2000
for a in a_list:
    a -= 1
    counts[a] += 1

accum = list(itertools.accumulate(counts))
for a in a_list:
    a -= 1
    if a == 0:
        continue
    ans += accum[a - 1] * K * (K - 1) // 2
    ans %= MOD
print(ans)


Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
using namespace std;
long long n,k,a[1<<17],f,ans,sum;
main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<k;i++)
	{
		long long x;cin>>x;ans=sum=f=0;
		for(int r=0;r<n;r++)
		{
			sum+=a[r];
			while(f<=r&&sum>x)sum-=a[f++];
			ans+=r-f+1;
		}
		cout<<ans<<endl;
	}
}



Measured memory_bytes: 3844
#include<iostream>
using namespace std;
#define Maxnum 100000
int main() {
    int n;
    cin >> n;
    int a[Maxnum];
    int sum[Maxnum];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sum[0] = 0;
    sum[1] = abs(a[0] - a[1]);
    for (int i = 2; i < n; ++i) {
        sum[i] = min(sum[i-2] + abs(a[i] - a[i-2]), sum[i-1] + abs(a[i] - a[i-1]));
    }
    cout << sum[n-1] <<endl;
}

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

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

int main(void) {
    ll W, H, x, y;
    cin >> W >> H >> x >> y;

    double area = (W * H) / 2.0;
    // double area = (W * H) / 2.0f; // this is calculated as float then converted into double

    if (x * 2 == W && y * 2 == H) {
        printf("%.10f %d\n", area, 1);
    } else {
        printf("%.10f %d\n", area, 0);
    }

    return 0;
}


Measured memory_bytes: 256
import sys

p = [0] * 51
v = 0
for i in range(10):
    p[i] = p[36-i] = (i+3)*(i+2)*(i+1)//6

for i in range(10,19):
    p[i] = p[36-i] = (i+1)*(i+2)*(i+3)//6 - 2*(i-9)*(i-8)*(i-7)//3

for i in sys.stdin:
    print(p[int(i)])

Measured memory_bytes: 7512
#include <iostream>
using namespace std;
int main() {
    int h, w;
    while(1){
        cin >> h >> w;
        if (h == 0 && w == 0) break;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                if (i == 0 || i == h-1 || j == 0 || j == w-1){
                    cout << '#';
                }
                else {
                    cout << '.';
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3084
#include <cstdio>

using namespace std;
typedef long long LL;

const int N=1e5+10,Mod=1e9+7;

LL A,B,val[N];
int n,sum[N];

struct Bit
{
	#define lowbit(x) ((x)&(-(x)))
	int v[N],cset[N],cv[N],cnt;
	
	Bit() { for (int i=0;i<N;++i) v[i]=0; }
	
	void Clear()
	{
		while (cnt)
		{
			Add(cset[cnt],-cv[cnt],1);
			cnt--;
		}
	}
	
	void Add(int set,int value,bool fl=0)
	{
		if (!fl) { ++cnt; cset[cnt]=set; cv[cnt]=value; }
		set++;
		for (;set<N;set+=lowbit(set))
			v[set]=(v[set]+value)%Mod;
	}
	
	int Query(int set)
	{
		set++;
		int ret=0;
		for (;set;set-=lowbit(set))
			ret=(ret+v[set])%Mod;
		return ret;
	}
}bit1,bit2;

void Init()
{
	scanf("%d%lld%lld",&n,&A,&B);
	for (int i=1;i<=n;++i) scanf("%lld",&val[i]);
}

void Solve()
{
	bit1.Add(0,1); bit2.Add(0,1);
	int p1=1,p2=1;
	for (int i=1;i<n;++i)
	{
		while (val[i+1]-val[p1]>=B) p1++;
		int v2=bit1.Query(p1-1);
		if (val[i+1]-val[i]<A) bit1.Clear();
		
		while (val[i+1]-val[p2]>=A) p2++;
		int v1=bit2.Query(p2-1);
		if (val[i+1]-val[i]<B) bit2.Clear();
		
		bit2.Add(i,v2);
		bit1.Add(i,v1);
	}
	printf("%d\n",(bit1.Query(n)+bit2.Query(n))%Mod);
}

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

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

int main() {
  int n, m;
  cin >> n >> m;
  
  vector<vector<char>> a(n, vector<char>(n)), b(m, vector<char>(m));
  string s;
  int i, j, k, l;
  for(i = 0; i < n; i++){
    cin >> s;
    for(j = 0; j < n; j++){
      a.at(i).at(j) = s.at(j);
    }
  }
  for(i = 0; i < m; i++){
    cin >> s;
    for(j = 0; j < m; j++){
      b.at(i).at(j) = s.at(j);
    }
  }
  
  bool ans = true;
  for(i = 0; i <= n - m; i++){
    for(j = 0; j <= n - m; j++){
      ans = true;
      for(k = 0; k < m; k++){
        for(l = 0; l < m; l++){
          if(a.at(i + k).at(j + l) != b.at(k).at(l)){
            ans = false;
          }
        }
      }
      if(ans) break;
    }
    if(ans) break;
  }
  
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define N 1010
#define ll long long
const ll mod =1e9+7;

int main()
{
    char s[100];
    int n,k;
    scanf("%d%d%s",&n,&k,s+1);
    if(s[k]=='A')s[k]='a';
    else if(s[k]=='B')s[k]='b';
    else s[k]='c';
    cout<<s+1<<endl;
    return 0;
}


Measured memory_bytes: 256