akhauriyash/Code-Regression huggingface dataset:
// atcoder/abc124/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int fn(string s, int k)
{
  vector<pair<int, int>> v;
  {
    int cnt = 0;
    char prev = s[0];
    each (c, s) {
      if (prev != c) {
        v.push_back({prev - '0', cnt});
        cnt = 0;
        prev = c;
      }
      ++cnt;
    }
    v.push_back({(prev - '0'), cnt});
  }

  int mx = 0;
  each (i, v) {
    if (i.first == 1) {
      setmax(mx, i.second);
    }
  }

  int sum = 0;
  int z = 0;
  queue<pair<int, int>> q;
  each (i, v) {
    q.push(i);
    z += (i.first == 0);
    sum += i.second;
    while (q.size() && k < z) {
      pair<int, int> p = q.front();
      q.pop();
      z -= (p.first == 0);
      sum -= p.second;
    }
    setmax(mx, sum);
  }

  return mx;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  string s;
  while (cin >> n >> k >> s) {
    string t = s;
    replace(begin(t), end(t), '0', '@');
    replace(begin(t), end(t), '1', '0');
    replace(begin(t), end(t), '@', '1');
    string a = s;
    string b = t;
    reverse(begin(a), end(a));
    reverse(begin(b), end(b));
    // cout << fn(s, k) << endl;
    cout << max({fn(s, k), fn(t, k - 1), fn(a, k), fn(b, k - 1)}) << endl;
  }

  return 0;
}


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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int n = Integer.parseInt(str[0]);
    int l = Integer.parseInt(str[1]);
    int ans = 0;
    int min = Integer.MAX_VALUE;
    for(int i=1; i<=n; i++) {
      ans += l+i-1;
      if(Math.abs(l+i-1)<Math.abs(min)) {
        min = l+i-1;
      }
    }
    System.out.println(ans-min);
  }
}

Measured memory_bytes: 21200
#include <stdio.h>

int main(void)
{
  int a[4], b[4];
  int i, ad1, ad2;
  ad1 = ad2 = 0;

  scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]);
  scanf("%d%d%d%d", &b[0], &b[1], &b[2], &b[3]);

  for(i = 0; i < 4; i++){
    ad1 += a[i];
    ad2 += b[i];
  }

  if(ad1 > ad2)
    printf("%d\n", ad1);
  else if(ad2 > ad1)
    printf("%d\n", ad2);
  else
    printf("%d\n", ad1);

  return 0;
}

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

typedef long long ll;
using namespace std;
vector<int>ps;
int t;
bool dp[16005][16005];
bool go(int i, int pos){
	if(i == ps.size())
		return pos == t;
	if(dp[i][pos])
		return 0;
	dp[i][pos] = 1;
	if(go(i + 1, pos + ps[i]))
		return 1;
	if(go(i + 1, pos - ps[i]))
		return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	//	srand(time(NULL));
	int x = 0;
	string s; cin >> s;
	s += 'T';
	int tx, ty; cin >> tx >> ty;
	int ind = 0;
	while(ind < s.size() && s[ind] == 'F')
		x++, ind++;
	ind++;
	int c[2] = {0, 0}, ci = 1;
	vector<int>p[2];
	while(ind < s.size()){
		if(s[ind] == 'T'){
			if(c[ci])
				p[ci].push_back(c[ci]);
			c[ci] = 0;
			ci = 1 - ci;
		}
		else c[ci]++;
		ind++;
	}

//	for(int i = 0; i < p[0].size(); i++)
//		cerr << p[0][i] << ' ';
//	cerr << endl;
//	for(int i = 0; i < p[1].size(); i++)
//		cerr << p[1][i] << ' ';
//	cerr << endl;

	memset(dp, 0, sizeof dp);
	ps = p[0]; t = tx + 8000;
	if(!go(0, x + 8000)){
		cout << "No\n";
		return 0;
	}
//	cerr << "EEEEEEEH" << endl;
	memset(dp, 0, sizeof dp);
	ps = p[1]; t = ty + 8000;
	if(!go(0, 8000)){
		cout << "No\n";
		return 0;
	}

	cout << "Yes\n";
	return 0;
}


Measured memory_bytes: 250624
N = int(input())

f = 0
s = 0
index = 0
for i in range(N):
    a = int(input())
    if a > f:
        index = i
        s = f
        f = a
    elif a > s:
        s = a

for i in range(N):
    if i == index:
        print(s)
    else:
        print(f)

Measured memory_bytes: 4540
s = input()

max_acgt = ''
candidate = ''
for bs in s:
    if 'A' == bs or 'T' == bs or 'G' == bs or 'C' == bs:
        candidate += bs
    else:
        if len(max_acgt) < len(candidate):
            max_acgt = candidate
            candidate = ''
else:
    if len(max_acgt) < len(candidate):
            max_acgt = candidate
    print(len(max_acgt))


Measured memory_bytes: 2940
#include <cstdio>

int main(){
    char S[10];
    scanf("%s", S);

    int ans = 0;
    for (int i= 0; i < 4; ++i){
        if (S[i] == '+') ++ans;
        else --ans;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 5;
const ll MOD = 1e9 + 7;
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pis pair<ll,string>
#define F first
#define S second
#define LCM(a,b) ((a*b)/__gcd(a,b))
#define inf 1e15
#define test ll cse;cin>>cse;for(ll _i=1;_i<=cse;_i++)
#define PI 3.14159265
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const double EPS = 1E-9;
typedef vector< vector<double> > matrix;
typedef vector< vector<int> > array_2D;
typedef pair<int, pair<int, int> > ppi;
typedef vector<int> vi;

ll binaryExponentiation(ll x, ll n){
    ll result = 1LL;
    while(n > 0){
        if(n&1) result *= x;
        x = x*x;
        n >>= 1;
    }
    return result;
}
// 1000000000000000000


int main() {


    string s;
    cin >> s;

    if(s == "ABC")
        cout << "ARC\n";
    else
        cout << "ABC\n";

    return 0;
}

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

int N,X;
int m[100];

int main(){
  cin >> N >> X;
  int ans = N;
  for(int i=0; i<N; i++){
    cin >> m[i];
    X -= m[i];
  }
  sort(m,m+N);

  ans += X/m[0];
  cout << ans << endl;
}

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

using namespace std;

#define YES(n) cout << (n?"YES":"NO")<<endl;
#define Yes(n) cout << (n?"Yes":"No")<<endl;

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

    int ma=max({ a,b,c });
    cout << a + b + c - ma << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
x = list(map(int, input().split()))
ans = 10**9

for i in range(N-K+1):
    if x[i] * x[i+K-1] < 0:
        ans = min(ans, abs(x[i+K-1]) + abs(x[i]) + min(abs(x[i+K-1]), abs(x[i])))
    elif x[i] >= 0:
        ans = min(ans, x[i+K-1])
    else:
        ans = min(ans, abs(x[i]))

print(ans)


Measured memory_bytes: 14384
import java.util.Scanner;
public class Main {

	static int func(int num) {
		return(num * num);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner stdIn = new Scanner(System.in);
		final int range = 600;
		int d;

		while(stdIn.hasNext()) {
			d = stdIn.nextInt();
			int quantity = range / d;

			long area = 0;
			for(int r = 1; r < quantity; r++) {
				area += func(r * d) * d; 
			}

			System.out.println(area);
		}
	}

}

Measured memory_bytes: 17376
n = int(input())
list1 = list(map(int,input().split()))

mod = 10 ** 9 + 7
total = 0
y = sum(list1)

for i in range(0,n-1):
    y = y- list1[i]
    total += list1[i] * y % mod

total = total % mod
print(total)


Measured memory_bytes: 31680
using System;
using System.Linq;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
    var y = Math.Round(a.Average(), MidpointRounding.AwayFromZero);
    Console.WriteLine(a.Sum(x => (x - y) * (x - y)));
  }
}

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

#define REP(i, n) for (int i=0;i<int(n);++i)
#define EACH(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

struct HeavyLight {
  int pathCount,n;
  vector<int>size,parent,in,out,path,pathRoot;
  vector<vector<int> > tree;

  HeavyLight(vector<vector<int> > t)
    :pathCount(0),n(t.size()),size(n),parent(n),in(n),out(n),
     path(n),pathRoot(n),tree(t){
    int time=0;
    dfs(0,-1,time);
    buildPaths(0,newPath(0));
  }

  void dfs(int u, int p, int &k){
    in[u]=k++, parent[u]=p, size[u]=1;
    EACH(v,tree[u])if(*v!=p)dfs(*v, u, k),size[u]+=size[*v];
    out[u]=k++;
  }

  int newPath(int u){ pathRoot[pathCount]=u; return pathCount++; }

  void buildPaths(int u, int pt){
    path[u]=pt;
    EACH(v,tree[u])if(*v != parent[u])
      buildPaths(*v, 2*size[*v] >= size[u] ? pt : newPath(*v));
  }

  bool isAncestor(int p, int ch){
    return in[p] <= in[ch] && out[ch] <= out[p];
  }

  int lca(int a,int b){
    for(int root; !isAncestor(root=pathRoot[path[a]],b);a=parent[root]);
    for(int root; !isAncestor(root=pathRoot[path[b]],a);b=parent[root]);
    return isAncestor(a,b)?a:b;
  }
};

//Usage: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
int main(void){
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  vector<vector<int> >tree(n);
  
  REP(i,n){
    int k;
    cin >> k;
    REP(j,k){
      int ch;
      cin >> ch;
      tree[i].push_back(ch);
    }
  }

  HeavyLight hl = HeavyLight(tree);

  int q;
  cin >> q;
  while(q--){
    int u,v;
    cin >> u >> v;
    cout << hl.lca(u,v) << "\n";
  }
  
  return 0;
}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef long long lint;

int N, A, B;
lint dp[55][55], cnt[55][55];

int main() {
	cin >> N >> A >> B;
	
	memset(dp, 0, sizeof(dp));
	memset(cnt, 0, sizeof(cnt));
	cnt[0][0] = 1;
	
	for_(i,0,N) {
		lint v; cin >> v;
		for_(j,0,i+1) {
			if (cnt[i][j] == 0) continue;
			
			for_(b,0,2) {
				if (dp[i+1][j+b] < dp[i][j] + b * v) {
					cnt[i+1][j+b] = cnt[i][j];
					dp[i+1][j+b] = dp[i][j] + b * v;
				} else if (dp[i+1][j+b] == dp[i][j] + b * v) {
					cnt[i+1][j+b] += cnt[i][j];
				}
			}
		}
	}
	
	long double ans_v = 0;
	lint ans_c = 0;
	for_(i,A,B+1) {
		long double val = (long double)dp[N][i] / i;
		if (ans_v <= val) {
			if (ans_v < val) ans_c = cnt[N][i];
			else ans_c += cnt[N][i];
			ans_v = val;
		}
	}
	printf("%.9Lf\n%Ld\n", ans_v, ans_c);
}

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

long long int gcd(long long int x, long long int y){
 long long int tmp;
 long long int r;
 if(x > y){
    tmp = x;
    x = y;
    y = tmp;
  }
  r = y % x;
  while(r!=0){
    y = x;
    x = r;
    r = y % x;
  }
  return x;
}

map< int64_t, int64_t > prime_factor(int64_t n) {
  map< int64_t, int64_t > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main(){
    int64_t A,B;
    cin >> A >> B;
    int64_t G= gcd(A,B);
    int64_t loop=0;
    for(auto p : prime_factor(G))loop++;
    cout << loop+1 << endl;
}

Measured memory_bytes: 256
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

S=get_nsp.reverse
#S=["1"]*100000
N=S.size
MOD=2019
accum=array(N+1,0)
b=1
N.times do|i|
    accum[i+1]=(accum[i]+S[i].to_i*b)%MOD
    b*=10
    b%=MOD
end
kind=accum.tally
ans=0
kind.each do|key,val|
  ans+=val*(val-1)/2
end
puts ans

Measured memory_bytes: 28036
def main():
    n = int(input())
    # d,t,s = map(int, input().split())
    a = list(map(int, input().split()))
    # s = input()
    mod = 10**9+7

    s = sum(a)

    sm = 0

    for i in a:
        s -= i
        sm += i * s % mod

    print(sm % mod)


if __name__ == '__main__':
    main()


Measured memory_bytes: 105452
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;
	int num[5] = {a,b,c,d,e};
	int ans = -100;
	int pos = -1;
	int k;
	for(int i=0;i<5;i++)
	{
		int n;
		if(num[i]%10)n = 10-num[i]%10;
		else n=0;
		if(ans<n)
		pos = i , ans = n , k = num[i];
	}
	num[pos] = -1;
	int sum =k;
	for(int i=0;i<5;i++)
	{
		if(num[i]!=-1&&num[i]%10 )
		{
			num[i] -=(num[i]%10);
			num[i]+=10;
			sum+=num[i];
		}
		else if(num[i]!=-1)
		{
			sum+=num[i];
		}
	}
	cout<<sum<<endl;
 } 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
  int n;
  cin>>n;
  int h[n];
  int i,x,m=0,c=0;
  for(i=0;i<n;i++){
    cin>>x;
    if(m<=x){
      m=x;
      c++;
    }
  }
  cout<<c;
}
      
    

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

int main(){
  int N;cin>>N;
  const long mod=1000000007;
  bool prime[N+1];
  for(int i=0;i<=N;i++) prime[i]=true;
  vector<int> E;
  for(int i=2;i<=N;i++){
    if(prime[i]){
      for(int j=i*2;j<=N;j+=i) prime[j]=false;
      E.push_back(i);
    }
  }
  int L=E.size();//N以下なのでintでOK
    
 // long ans[N+1][L];
  long ans[L];
  for(int i=0;i<L;i++) ans[i]=1;
  for(int n=2;n<=N;n++){
    int F=n;//バグのもと
    for(int j=0;j<L;j++){
      while(F%E[j]==0){
        F /=E[j];
        ans[j]++;
      }
      if(F==1) break;
    }
  }
  long count=1;
  for(int i=0;i<L;i++){
    count *=ans[i];
    count %=mod;
  }
  cout<<count<<endl; 
}
    


Measured memory_bytes: 3588
N = int(input())

P = [[int(_) for _ in input().split()] for n in range(N)]

X = []
Y = []
for x, y in P:
    X.append(x)
    Y.append(y)
mx = (min(X) + max(X)) // 2
my = (min(Y) + max(Y)) // 2

Qx = []
Qy = []
for x, y in P:
    x, y = x-mx, y-my
    Qx.append(x+y)
    Qy.append(x-y)

ax = max(Qx) - min(Qx)
ay = max(Qy) - min(Qy)
ans = max(ax, ay)
print(ans)


Measured memory_bytes: 61432
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
class Program
{
    static void Main()
    {
        Console.ReadLine();
        int[] inputs = Console.ReadLine().Split(' ')
                                    .Select(val => int.Parse(val))
                                    .ToArray();
        Heap maxHeap = new Heap(inputs);
        maxHeap.BuildMaxHeap();
        maxHeap.Display();
    }
}

class Heap
{
    private const int MaxSize = 500000;
    public int Count {get; set;} // = 0;
    private int[] elements;
    public int this[int i]
    {
        get {return elements[i];}
        set {elements[i] = value;}
    }
    public Heap() : this(MaxSize) {}
    public Heap(int size)
    {
        elements = new int[size];
        Count = size;
    }
    public Heap(int[] array)
    {
        Count = array.Length;
        elements = new int[Count];
        for (int i = 0; i < Count; i++)
        {
            elements[i] = array[i];
        }
    }
    private int LeftOf(int i)
    {
        int val = 2 * (i + 1) - 1;
        return val < Count ? val : -1;
    }
    private int RightOf(int i)
    {
        int val = 2 * (i + 1);
        return val < Count ? val : -1;
    }
    public void BuildMaxHeap()
    {
        for (int i = Count / 2 - 1; i >= 0 ; i--)
        {
            Modify(i);
        }
    }
    private void Modify(int i)
    {
        int l = LeftOf(i);
        int r = RightOf(i);
        int largest = i;
        if(l != -1 && elements[l] > elements[i]) largest = l;
        if(r != -1 && elements[r] > elements[largest]) largest = r;
        if(largest != i)
        {
            Swap(i, largest);
            Modify(largest);
        }
    }
    private void Swap(int i, int j)
    {
        int tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }
    public void Display()
    {
        for (int i = 0; i < Count; i++)
        {
            Console.Write(" " + elements[i]);
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 60788
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vvvi = vector<vvi>; // intの2次元の型に vvi という別名をつける
const ll llMAX=9223372036854775807LL; 
const ll llMIN=-9223372036854775808LL;

ll n,k,x,y;

int main(){
  ll ans=0;
  cin >> n ;
  ll ans3=1;
  ll ans2=1;
  ll ans1=1;
  REP(i,n){
    ans3=ans3*10%MOD;
    ans2=ans2*9%MOD;
    ans1=ans1*8%MOD;
  }

  ans=(ans3-ans2*2+ans1+MOD*2)%MOD;

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

Measured memory_bytes: 3628
N, Q = map(int, input().split())
d = [0 for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[b] = a
ans = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

for i in range(1, N):
    ans[i] += ans[d[i]]

print(*ans)

Measured memory_bytes: 66764
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
#define bit(n,k) ((n>>k)&1) //*n no k bit me 1 or 0*/

const int mx=200010;
const ll mod=1e9+7;

struct LazySegmentTree{
private:
   int n;
   vector<ll> node,lazy;
public:
   LazySegmentTree(int sz,ll init=0){
      n=1;
      while(n<sz)n*=2;
      node.resize(2*n-1,init);
      lazy.resize(2*n-1,0);
   }
 
   void eval(int k,int l,int r){
      if(lazy[k]!=0)node[k]+=lazy[k];
      if(r-l>1){
          lazy[2*k+1]+=lazy[k];
          lazy[2*k+2]+=lazy[k];
      }
      lazy[k]=0;
   }
      //[a,b)にxを加算
   void add(int a,int b,ll x,int k=0,int l=0,int r=-1){
       if(r<0)r=n;
       eval(k,l,r);
       if(r<=a||b<=l)return;
       if(a<=l&&r<=b){
          lazy[k]+=x;
          eval(k,l,r);
       }
       else {
          add(a,b,x,2*k+1,l,(l+r)/2);
          add(a,b,x,2*k+2,(l+r)/2,r);
          node[k]=min(node[2*k+1],node[2*k+2]);
        }
   }
   //[a,b)でのminを返す
   ll get(int a,int b,int k=0,int l=0,int r=-1){
      if(r<0)r=n;
      eval(k,l,r);
      if(r<=a||b<=l)return longinf;
      if(a<=l&&r<=b)return node[k];
      ll xl=get(a,b,2*k+1,l,(l+r)/2);
      ll xr=get(a,b,2*k+2,(l+r)/2,r);
      return min(xl,xr);
   }
};
 
vector<ll> dp(mx,longinf);

int main(){
  int n,m;
  cin >> n >> m;
  vector<pair<ll,ll>> a[n+1];
  ll ans=0;
  rep(i,m){
    int x,y,z; cin>>x>>y>>z;
    ans+=z;
    a[y].emplace_back(x,z);
  }

  LazySegmentTree sg(n+1,0);
  dp[0]=0;
  rep(i,n){
    dp[i+1]=dp[i];
    sg.add(i+1,i+2,dp[i+1]);
    for(auto p:a[i+1]){ sg.add(0,p.F,p.S); }
    dp[i+1]=min(dp[i+1],sg.get(0,i+1));
  }

  
  ans -= dp[n];
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 20992
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,x,y,i,j,dd[N],p[N];
vector<int>e[N],p0,p1;
int nxt(int x,int fa){for(int y:e[x])if(e[y].size()>1 && y!=fa)return y;return 0;}
int main(){
	scanf("%d",&n);for(i=1;i<n;++i)scanf("%d%d",&x,&y),e[x].push_back(y),e[y].push_back(x);
	if(n==2){puts("1 2");return 0;}
	for(i=1;i<=n;++i)for(int x:e[i])dd[i]+=e[x].size()>1;
	for(i=1;i<=n;++i)if(dd[i]>2){puts("-1");return 0;}
	for(i=1;i<=n;++i)if(dd[i]<2 && e[i].size()>1){
		auto&v=p0.empty()?p0:p1;int lst=0;
		for(x=i;x;v.push_back(x),y=x,x=nxt(x,lst),lst=y);
		for(int&x:v)x=e[x].size()-2;
	}
	if(!p1.empty() && p0>p1)p0=p1;
	p[1]=1;p[n]=n;x=y=1;
	for(i=0;i<p0.size();++i){
		p[x+p0[i]+1]=++y;
		for(j=0;j<p0[i];++j)p[x+j+1]=++y;x+=p0[i]+1;
	}
	for(i=1;i<=n;++i)printf("%d%c",p[i],i==n?'\n':' ');
	return 0;
}

Measured memory_bytes: 7928
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

char a[105],b[105],c[105];
int main()
{
	scanf("%s %s %s",&a,&b,&c);
	printf("%c%c%c",a[0],b[0],c[0]);
	return 0;
	}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
  int x, y;
  cin >> x >> y;
  for (int i = 0; i <= x; i++) {
    int j = x - i;
    if (i * 4 + j * 2 == y) {
      return cout << "Yes" << endl, 0;
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 3632
def main():
    N = int(input())
    data = list(map(int, input().split()))

    indexed_data = list(zip(range(1, N + 1), data))

    indexed_data.sort(key=lambda x: x[1])

    for index, _ in indexed_data:
        print(index, end=' ')

    print()


if __name__ == '__main__':
    main()


Measured memory_bytes: 62908
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    rep(i,n-1){
        if(i%2 == 1) continue;
        string t = "", u = "";
        rep(j,i/2){
            t += s[j];
        }
        for(int j = i/2; j < i; j++){
            u += s[j];
        }
        if(t == u) chmax(ans, i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        long n = in.nextLong();
        long a = in.nextLong();
        long b = in.nextLong();
        long ans = (n/(a+b))*a;
        n%=(a+b);
        ans+=Math.min(n,a);
        out.println(ans);
    }
    
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 22996
from math import sqrt

while True:
    n = int(input())
    if n == 0:
        break
    
    lst = list(map(float,input().split()))
    ave = sum(lst) / len(lst)
    alpha = 0.0
    for i in lst:
        alpha += (ave - i)**2
    S = sqrt((alpha/n))
    print(S)


Measured memory_bytes: 5784
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m;
pair<int,int>val[200010];
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		for(int i=1;i<=n;i++){
			val[i].second=i;
			val[i].first=i;
		}
		for(int i=1;i<=m;i++){
			int temp;
			scanf("%d",&temp);
			val[temp].first=-i;			
		}
		sort(val+1,val+1+n);
		for(int i=1;i<=n;i++)
			printf("%d\n",val[i].second);
	}
}

Measured memory_bytes: 4312
import std.algorithm,
       std.string,
       std.array,
       std.range,
       std.stdio,
       std.conv;

void main() {
  int n = readln.chomp.to!int;
  int m = 1;

  while (m < n) {
    m *= 2;
  }

  writeln(m / (m == n ? 1 : 2));
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();
static constexpr ll MOD = 1000000007;

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);

ll memo[2005][2005];

ll comb(int i, int j) {
  if (memo[i][j] > 0) return memo[i][j];

  ll l = (i > 0 && i > j) ? comb(i - 1, j) : 0;
  ll r = (i > 0 && j > 0) ? comb(i - 1, j - 1) : 0;

  return memo[i][j] = (l + r) % MOD;
}

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);

  memo[0][0] = 1;

  rep(i, 1, K + 1) {
    ll ans = (comb(N - K + 1, i) * comb(K - 1, i - 1)) % MOD;
    cout << ans << endl;
  }

  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}


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

int main(){

ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a,b;
    cin>>a>>b;
    if((a>=1&&a<=9)&&(b>=1&&b<=9))
    cout<<a*b;
    else
    cout<<-1;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	char lj;
	cin>>lj;
	if(lj=='a')
	cout<<'b';
	if(lj=='b')
	cout<<'c';
	if(lj=='c')
	cout<<'d';
	if(lj=='d')
	cout<<'e';
	if(lj=='e')
	cout<<'f';
	if(lj=='f')
	cout<<'g';
	if(lj=='g')
	cout<<'h';
	if(lj=='h')
	cout<<'i';
	if(lj=='i')
	cout<<'j';
	if(lj=='j')
	cout<<'k';
	if(lj=='k')
	cout<<'l';
	if(lj=='l')
	cout<<'m';
	if(lj=='m')
	cout<<'n';
	if(lj=='n')
	cout<<'o';
	if(lj=='o')
	cout<<'p';
	if(lj=='p')
	cout<<'q';
	if(lj=='q')
	cout<<'r';
	if(lj=='r')
	cout<<'s';
	if(lj=='s')
	cout<<'t';
	if(lj=='t')
	cout<<'u';
	if(lj=='u')
	cout<<'v';
	if(lj=='v')
	cout<<'w';
	if(lj=='w')
	cout<<'x';
	if(lj=='x')
	cout<<'y';
	if(lj=='y')
	cout<<'z';
	return 0;
}

Measured memory_bytes: 256
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	string s;
	
	cin >> s;

	if (s == "Sunny")
	{
		cout << "Cloudy" << endl;
	}
	else if (s == "Cloudy")
	{
		cout << "Rainy" << endl;
	}
	else if (s == "Rainy")
	{
		cout << "Sunny" << endl;
	}

	
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int m,n,i,sum=0;
    scanf("%d %d",&m,&n);
    int a;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a);
        sum=sum+a;
    }
    if(sum>=m)
       printf("Yes");
   else
       printf("No");

}

Measured memory_bytes: 128
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N, M;
    scan(N, M);

    auto a = new int[](M);
    auto open = new int[](M);

    foreach (i ; 0 .. M) {
        int ai, bi;
        scan(ai, bi);
        a[i] = ai;
        auto t = readln.split.to!(int[]);
        t[] -= 1;
        foreach (ti ; t) {
            open[i] |= (1 << ti);
        }
    }

    auto dp = new int[](1 << N);
    dp[] = inf;
    dp[0] = 0;

    foreach (s ; 0 .. 1 << N) {
        foreach (i ; 0 .. M) {
            chmin(dp[s | open[i]], dp[s] + a[i]);
        }
    }

    debug {
        writeln(dp);
    }

    auto ans = dp[(1 << N) - 1];
    writeln(ans < inf ? ans : -1);
}






void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


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

int main() {
	int a,b;
	cin >> a >> b;
	if (a == 1)a = 14;
	if (b == 1)b = 14;
	if (a < b) {
		cout << "Bob" << endl;
	}else {
		if (a > b) {
		cout << "Alice" << endl;
		}
		else
		{
		cout << "Draw" << endl;
		}
	}
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        double ans =0;

        for(int i = 0;i< N;i++){

            int count =0;
            int point = i+1;
            while(point < K){
                point = 2 * point;
                count++;
            }
            ans += Math.pow(0.5,count);

        }
        System.out.println(ans / N);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int res=0;
    int n,d,x;
    int a[100];
    cin >> n;
    cin >> d >> x;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<n;i++){
        res+=floor((d-1)/a[i])+1;
    }
    cout << res+x << endl;
}

Measured memory_bytes: 256
package main             
 
 import (
     "fmt"
 )
 
 func main() {
     var fw, fh, w, h, n int
     fmt.Scan(&w, &h, &n)
     for i := 0; i < n; i++{
         var x, y, i int
         fmt.Scan(&x, &y, &i)
         switch i {
         case 1:
             if fw < x {
                 fw = x
             }
         case 2:
           if x < w {
                w = x
            }
        case 3:
            if fh < y {
                fh = y
            }
        case 4:
            if y < h {
                h = y
            }
        }
    }
    val1 := w - fw
    val2 := h - fh
    if val1 < 0 {
        val1 = 0
    }
    if val2 < 0 {
        val2 = 0
    }
    fmt.Println(val1 * val2)
}                              

Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int main(){
  string s;
  while (cin >> s) {
    if (s == "0") break;

    int sum = 0;
    for (int i = 0; i < s.size(); i ++) {
      sum += s[i] - '0';
    }

    cout << sum << endl;
  }
}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;

  int x_diff = x2 - x1;
  int y_diff = y2 - y1;

  cout << x2 - y_diff <<  ' ' << y2 + x_diff << ' ' << x1 - y_diff << ' ' << y1 + x_diff << "\n";

  return 0;
}

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

int parent[200005], ranks[200005];

void initset(int n)
{
    for (int i = 0; i < n; i++)
    {
        parent[i] = i;
        ranks[i] = 0;
    }
}

int findSet(int x)
{
    if (parent[x] == x)
        return x;

    parent[x] = findSet(parent[x]);

    return parent[x];
}

bool sameSet(int x, int y)
{
    return findSet(x) == findSet(y);
}

void mergeSet(int x, int y)
{
    x = findSet(x);
    y = findSet(y);
    if (ranks[x] > ranks[y])
    {
        parent[y] = x;
    }
    else
    {
        parent[x] = y;
        if (ranks[x] == ranks[y])
        {
            ranks[y]++;
        }
    }
}

int main()
{

    int n, m;
    cin >> n >> m;

    initset(n + m + 5);

    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++)
        {
            int lang;
            cin >> lang;
            mergeSet(i + 1, n + lang);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (!sameSet(i, 1))
        {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";

    return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,ans;
long long a[102],b[102],c[102],book[102],last;
int main()
{
	ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	for(int i=1;i<n;i++)
		scanf("%lld",&c[i]);
	for(int i=1;i<=n;i++)
	{
		ans+=b[a[i]];
		book[a[i]]=1;
		if(last==a[i]-1&&a[i]>1)
			ans+=c[a[i]-1];
		last=a[i];
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
S = input()
prev = True
ans = 0
cnt = 0
for i in range(3):
  if S[i] == 'R':
    if prev:
      cnt += 1
    else:
      prev = True
      cnt = 1
  else:
    ans = max(ans, cnt)
    cnt = 0
    prev = False
print(max(ans, cnt))

Measured memory_bytes: 9116
var input = '';
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  input += chunk;
});

readable.on( 'end', function() {
  var data = input.split( "\n" );
  
  var output = [];
  for( var i=0; i<data.length; i++ ) {
      var nums = data[i].split( '' ).map( Number );
      if( 0 == nums[0] ) { break; }
      
      var sum = 0;
      for( var j=0; j<nums.length; j++ ) {
        sum += nums[j];
      }
      output.push( sum );
  }
  console.log( output.join( '\n' ) );
});
 

Measured memory_bytes: 8940
#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-10;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


//ここから編集
ll GCD(ll a, ll b){
    
    if(b == 0) return a;
    return GCD(b, a%b);
}

template<typename T = int> struct BIT{
  vector<T> node;

  int N;
  BIT(int n){
    N = n;
    node.resize(N+1);
  }

  void add(int i, T x){
    i++;
    while(i <= N){
      node[i] += x;
      i += (i & -i);
    }
  }

  T sum(int i){
    T res = 0;
    while(i > 0){
      res += node[i];
      i -= (i & -i);
    }
    return res;
  }

  

};
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N, M; cin >> N >> M;
  vector<vector<ll>> vp(100010);

  REP(i,N){
    ll a, b;cin >> a >> b;
    if(M-a < 0)continue;
    vp[M-a].push_back(b);
  }

  priority_queue<ll> pq;
  ll ans = 0;
  for(int i=M; i>=0; i--){
    for(int j=0; j < vp[i].size(); j++){
      pq.push(vp[i][j]);
    }

    if(pq.size()){
      ans += pq.top();
      pq.pop();
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 8712
#include <iostream>

int main()
{
  int n, k, x, y;
  std::cin >> n >> k >> x >> y;
  if (n > k)
  {
    std::cout << k * x + (n - k) * y << std::endl;
  }
  else
  {
    std::cout << n * x << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int num[] = { 0,2,5,5,4,5,6,3,7,6 };
int f[10005], tmp, a[10];
map<int, int>mp;
string ans[10005];
int main()
{
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> tmp;
		mp[num[tmp]] = max(mp[num[tmp]], tmp);
	}
	m = mp.size(); tmp = 0;
	for (auto i : mp)a[tmp++] = i.second;
	sort(a, a + m);
	memset(f, -1, sizeof(f)); f[0] = 0;
	for (int i = 0; i <= n; i++)ans[i] = "";
	for (int i = 0; i < m; i++)
		for (int j = num[a[i]]; j <= n; j++)
			if (f[j - num[a[i]]] >= 0 && f[j] <= f[j - num[a[i]]] + 1)
			{
				f[j] = f[j - num[a[i]]] + 1;
				ans[j] = ans[j - num[a[i]]] + char('0' + a[i]);
			}
	sort(ans[n].begin(), ans[n].end(), greater<int>());
	cout << ans[n] << endl;
	return 0;
}

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

#define pb(s) push_back(s)
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PI 3.14159265358979323846264338327950L


typedef long long ll;


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

    int k,s;
    cin>>k>>s;
    int cnt=0;
    for(int i=0;i<=k;++i){
        for(int j=0;j<=k;++j){
            if(s-(i+j)<=k&&s-(i+j)>=0){
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
   int N,K,X,Y;
   cin >> N;
   cin >> K;
   cin >> X;
   cin >> Y;
   if(N < K) {
     cout << N*X << endl;
     return 0;
   }
   int result = K*X + (N-K)*Y;
   cout << result << endl;
   return 0;
}

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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007
#define PI 3.141592653589793238462643383

signed main()
{
	init();
	solve();
}

vector<ll> v(3);

void init()
{
	rep(i, 3) cin >> v[i];
	sort(all(v));
}

void solve()
{
	rep(i, 3) {
		if (v[i] % 2 == 0) {
			cout << 0 << endl;
			return;
		}
	}
	cout << v[0] * v[1] << endl;
}



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

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> r(n);
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    r.at(i) = {a+b, b};
  }
  
  sort(r.begin(), r.end());
  int lastr = -2 * pow(10, 9), ans = 0;
  for(int i = 0; i < n; i++){
    int len = r.at(i).second, lef = r.at(i).first - 2 * len;
    if(lastr > lef) continue;
    ans++, lastr = r.at(i).first;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3976
import heapq

N, M = list(map(int,input().split()))
A = list(map(int,input().split()))

A = list(map(lambda x:-x,A))

heapq.heapify(A)

for i in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A,x/2)

ans = 0

for i in range(N):
    x = heapq.heappop(A)
    ans += int(-x)

print(ans)

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

void solve()
{
  string s;
  cin >> s;
  for(int i = 0; i < s.length(); i += 2)
  {
    cout << s[i];
  }
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3608
<?php
	fscanf(STDIN, "%d", $N);
	$ans = 0;

	for($i = $N; $i > 103; $i--){
		if($i % 2 === 0){
			continue;
		}
		$cnt = 0;
		for($j = 1; $j <= $i; $j += 2){
			if($i % $j === 0){
				$cnt++;
			}
		}

		if($cnt === 8){
			$ans++;
//           	print $i."\n";
		}
	}

	print $ans;
?>

Measured memory_bytes: 3700
// https://atcoder.jp/contests/abcXXX/tasks/abcXXX_x

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

static const ll INF = 1001001001;

void debug_out() {};
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif

struct C1 {
        ll N_{};
    vector<ll> v_{};
    explicit C1(vector<ll> v) : N_(v.size()), v_(move(v)){}
    ll resolve() {
        ll sum = 0;
        for(ll i=0; i < N_; ++i) {
            for(ll j=0; j < i; ++j) {
                sum += v_[i] * v_[j];
            }
        }
        return sum;
    }
};

int main() {
    ll N;
    cin >> N ;
    vector<ll> v{};
    for (int i=0; i < N; ++i) {
        ll x;
        cin >> x;
        v.emplace_back(x);
    }
    C1 c{move(v)};
    cout << c.resolve() << endl;
    debug(c.resolve());
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int isPrime(int);

int main(){
  int i, n, cnt=0;
  int a;
  
  scanf("%d", &n);
  for(i=0;i<n;i++) {
    scanf("%d", &a);
    cnt+=isPrime(a);
  }
  printf("%d\n", cnt);
  
  return 0;
}

int isPrime(int x)
{
  int i;
  if(x==2) return 1;
  if(x%2==0) return 0;
  for(i=3;i*i<=x;i+=2) 
    if(x%i==0) return 0;
  return 1;
}



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

int i;
long long a, b, n, mx, mn;

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

  cin >> n >> a >> b;

  if(n == 1 && a != b) return cout << "0\n", 0;

  if(a > b) return cout << "0\n", 0;

  mx = a + (n - 1) * b;
  mn = a * (n - 1) + b;

  cout << mx - mn + 1 << '\n';

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  long long X;
  cin >> X;
  long long money = 100;
  int ans = 0;
  while(money < X)
  {
    money *= 1.01;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
H,W = map(int,input().split())
S = []
for i in range(H):
  S.append(input())

m = [[0 for i in range(W)] for j in range(H)]
#yoko
for i in range(H):
  s = S[i]
  mar = 0
  cnt = 0
  for j in range(W):
    if s[j] == ".":
      cnt += 1
    if s[j] == "#":
      for k in range(mar,j):
        m[i][k] += cnt
      cnt = 0
      mar = j+1    
    #グリッドの端の処理
    if j == W-1 and s[j] == ".":
      for k in range(mar,j+1):
        m[i][k] += cnt


#tate      
for i in range(W):
  mar = 0
  cnt = 0
  for j in range(H):
    if S[j][i] == ".":
      cnt += 1
    if S[j][i] == "#":
      for k in range(mar,j):
        m[k][i] += cnt
      cnt = 0
      mar = j+1 
    #グリッドの端の処理
    if j == H-1 and S[j][i] == ".":
      for k in range(mar,j+1):
        m[k][i] += cnt


ans = 0
for i in range(H):
  ans = max(ans,max(m[i]))
print(ans-1)  

Measured memory_bytes: 102488
#include <bits/stdc++.h>
using namespace std;
int n, k, a[100020], z = 1e9;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i + k - 1 < n; i++) {
		z = min(z, a[i + k - 1] - a[i] + min(abs(a[i]), abs(a[i + k - 1])));
	}
	printf("%d\n", z);
	return 0;
}

Measured memory_bytes: 640