akhauriyash/Code-Regression huggingface dataset:
# include <stdio.h>
# include <math.h>
int main ()
{
	int a,b,c;
	while (scanf("%d%d%d",&a,&b,&c)==3&&a)
	     {
	     	int s[6]={0};
	     	s[0]=fabs(a-b)+fabs(b-c);
	     	s[1]=fabs(a-c)+fabs(c-b);
	     	s[2]=fabs(b-a)+fabs(a-c);
	     	s[3]=fabs(b-c)+fabs(c-a);
	     	s[4]=fabs(c-a)+fabs(a-b);
	     	s[5]=fabs(c-b)+fabs(b-a);
	     	int min =0,i;
	     	for (i=1;i<6;++i)
	     	   if (s[min]>s[i])
	     	     min =i;
	     	printf ("%d\n",s[min]);
	     }
}

Measured memory_bytes: 128
a,b=[int(i) for i in input().split()]

x=list()
y=list()

for i in range(a):
    l=input()
    x.append(list(l))
    y.append(x[i][:b])

z=[["" for i in range(b)] for j in range(a)]
for i in range(a):
    for j in range(b):
        if y[i][j]=='#':
            z[i][j]='#'
        else:
            n=0
            if i+1<a:
                    if y[i+1][j]=="#":
                         n+=1
            if j+1<b:
                    if y[i][j+1]=="#":
                         n+=1
            if i+1<a and j+1<b:
                    if y[i+1][j+1]=="#":
                         n+=1
            if i-1>=0:
                    if y[i-1][j]=="#":
                         n+=1
            if j-1>=0:
                    if y[i][j-1]=="#":
                         n+=1
            if i-1>=0 and j-1>=0:
                    if y[i-1][j-1]=="#":
                         n+=1
            if i+1<a and j-1>=0:
                    if y[i+1][j-1]=="#":
                         n+=1
            if i-1>=0 and j+1<b:
                    if y[i-1][j+1]=="#":
                         n+=1
            z[i][j]=str(n)
        #print(i,j,z[i][j])
    print("".join(z[i]))


Measured memory_bytes: 3188
def dgsm(n):
    x=0
    while n>0:
        x+=n%10
        n//=10
    return(x)
ans=0
n,a,b=map(int, input().split())
for i in range(1,n+1):
    if a<=dgsm(i)<=b:
        ans+=i
print(ans)

Measured memory_bytes: 3060
N, M = map(int, input().split())
A = list(map(int, input().split()))

count = 0
sum_total = sum(A)

for i in range(N):
    if (A[i] >= (sum_total /(4*M))):
        count=count+1


if count >= M:
    print("Yes")
else:
    print("No")







Measured memory_bytes: 2940
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define _ << " _ " <<
#define TRACE(x) cerr << #x << " = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug
//#define TRACE(x)

using namespace std;

const int INF = 1e9;

typedef long long llint;

int iter = 0;

int solve(int a, int b, int c) {
  if (++iter > 1000000)
    return INF;
  if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1)
    return 0;
  return solve((b+c)/2, (a+c)/2, (a+b)/2) + 1;
}

int main(void) {
  int a, b, c;
  scanf("%d %d %d",&a,&b,&c);
  int sol = solve(a,b,c);
  if (sol > INF)
    sol = -1;
  printf("%d\n",sol);
  return 0;
}


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

int main(){
  int N; cin >> N;
  vector<int> s(2*N);
  int ans = 0;
  
  for(int i = 0; i < 2*N; i++){
    cin >> s[i];
  }
  sort(s.begin(), s.end());
  
  for(int i = 0; i < N; i++){
    ans += s[2*i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main(){
  string s,str1,str2;
  cin>>s;
  int n =s.size();
  int half;
  if (n%2==0){ 
    half=n/2;
str1=s.substr(0,half);
str2=s.substr(half,half);
     }else {
     half =(n-1)/2;
 str1=s.substr(0,half);
str2=s.substr(half+1,half);
                   }
  string t=s;
  reverse(s.begin(),s.end());
  string t1=str1;
  reverse(t1.begin(),t1.end());
    string t2=str2;
  reverse(t2.begin(),t2.end());
  if (s==t && t1==str1 && t2==str2){
    cout <<"Yes";
  }else {
    cout <<"No";
  }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, int>;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  vector<P> v;
  for(int i = 0; i < n; i++){
    ll a;
    int b;
    cin >> a >> b;
    v.emplace_back(a, b);
  }
  sort(v.begin(), v.end());
  int rest = m;
  ll ans = 0;
  for(P& p : v){
    if(rest > p.second){
      rest -= p.second;
      ans += p.first * p.second;
    }
    else{
      ans += p.first * rest;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2420
N,M = map(int,input().split())
A = set([int(input()) for i in range(M)])
MOD = 10**9+7

if 0 in A:
    print(0)
    exit()

dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
    if i+1 not in A:
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    if i+2 <= N and i+2 not in A:
        dp[i+2] += dp[i]
        dp[i+2] %= MOD
print(dp[-1])


Measured memory_bytes: 56664
#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}

int h,w,K;
int sim(int n){
  int sum = w * n;
  
  for(int i=0;i<w;i++){
    int a = (h - n) - n;
    if(a < 0 && sum > K) sum+=a;
    else if(a >=0 && sum < K) sum += a;
  }
  return sum == K;
}

signed main(){

  cin>>h>>w>>K;
  
  int ans = 0;
  for(int i=0;i<h;i++)ans |= sim(i);
  cout<<(ans? "Yes":"No")<<endl;
  

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<math.h> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n;
int len[10000+100];
char s[10000+100][100];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		len[i]=strlen(s[i]);
	}
	ll a=0,b=0,sum=0;
	int ss=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i][0]=='B'&&s[i][len[i]-1]=='A')
		{
			ss++;
		}
		else if(s[i][0]=='B') 
		{
			b++;
		}
		else if(s[i][len[i]-1]=='A') 
		{
			a++;
		}
		for(int j=0;j<len[i]-1;j++)
		{
			if(s[i][j]=='A'&&s[i][j+1]=='B') sum++;
		}
	}
//	printf("%d %d %d %d\n",ss,sum,a,b);
	if(ss==0)
	{
		sum=sum+min(a,b);
	}
	else
	{
		if(b>0&&a>0)
		{
			sum=sum+ss+1+min(a-1,b-1);
		}
		else if((a>0&&b==0)||b>0&&a==0)
		{
			sum=sum+ss;
		}
		else if(a==0&&b==0)
		{
			sum=sum+ss-1;
		}
	}
	printf("%lld\n",sum);
	return 0;
}


Measured memory_bytes: 1280
import java.util.*;
import java.lang.*;
import java.io.*;
import java.awt.Point;

class Main{

      public static void main(String args[])throws IOException
    {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(in.readLine());	
	LinkedList<Point> list = new LinkedList<Point>();	
	for(int i=0;i<N;i++)
	    {
		String line = in.readLine();
		int A,B;
		A = Integer.parseInt(line.substring(0,line.indexOf(" ")));
		B = Integer.parseInt(line.substring(line.indexOf(" ")+1));
		list.add(new Point(B-A,B));
	    }
	

	Collections.sort(list,new Comparator<Point>(){
                        @Override
                            public int compare(Point a,Point b)
                        {
			    if(a.x < b.x)
				{
				    return 1;
				}	
			    else if(a.x == b.x)
				{
				    return 0;
				}	
			    else
				{
				    return -1;
				}	    
                        }
	    });

	int cnt = 0;
	for(int i=0;i<list.size();i++)
	    {
		if(list.get(i).x >= 0)
		    {
			cnt++;
			for(int j=i+1;j<list.size();j++)
			    {
				
				if(list.get(j).y > list.get(i).x)
				    {
					int dif = Math.min(list.get(j).y-list.get(i).x,list.get(i).y-list.get(i).x);
					Point p = list.get(j);
					list.set(j,new Point(p.x-dif,p.y));
					
				    }
				

			    }

			Collections.sort(list,new Comparator<Point>(){
				@Override
				    public int compare(Point a,Point b)
				{
				    if(a.x < b.x)
				{
				    return 1;
				}	
				    else if(a.x == b.x)
					{
					    return 0;
					}	
				    else
					{
				    return -1;
					}	    
				}
			    });
			
		    }
		
		
		
	    }

	
	System.out.println(cnt);	

    }

}

Measured memory_bytes: 9624
#include<stdio.h>
int main(void){
    int K;
    scanf("%d",&K);
    int n = 0;
    for(int i = 1; i <= K; i = i+2){
        for(int j = 2; j <= K; j = j+2){
            // printf("(%d, %d)",i,j);
            n++;
        }
        // printf("\n");
    }
    printf("%d\n",n);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
	
	char S[4]{};
	char T[4]{};

	cin >> S >> T;

	int count = 0;

	if (S[0] == T[0]) count++;
	if (S[1] == T[1]) count++;
	if (S[2] == T[2]) count++;

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repa(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define COUT(x) cout << (x) << endl
#define _GLIBCXX_DEBUG

int main(){
  
  string a, b, c;
  cin >> a >> b >> c;
  if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0])
    cout << "YES" << endl;
  else cout << "NO" << endl;
  
}

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

int main() {
  int N;
  cin >> N;
  int F = 0;
  string color,result;
  for(int i = 0; i < N; i++){
    cin >> color;
    if (color == "Y"){
      F = 1;
    }
  }
  if (F == 0){
    result = "Three";
  }else{
    result = "Four";
  }
  cout << result << endl;
}

Measured memory_bytes: 256
D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
res = 0
ans = [-1]*D
llst = [0]*26

def calc(d,x):
    day = d+1
    res = s[d][x]
    for i in range(26):
        if x == i: continue
        res -= c[i]*(day-llst[i])
    return res

for i in range(D):
    mx = -1
    mxv = -float("inf")
    for j in range(26):
        v = calc(i,j)
        if v >= mxv:
            mx = j
            mxv = v
    ans[i] = mx+1
for i in range(D): print(ans[i])

Measured memory_bytes: 9340
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long ans = 0;
	int N;
	cin >> N;

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

	cout << ans;

	return 0;
}


Measured memory_bytes: 3584
let harmony a b =
  let harmony_hojo a b =
    if (a + b) mod 2 = 0 then Some ((a + b) / 2)
                         else None
  in
    match harmony_hojo a b with
        None -> "IMPOSSIBLE"
      | Some (p) -> string_of_int p

let a, b = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> (a, b))
let () = Printf.printf "%s\n" (harmony a b)

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

int main(){
    int k; //k番目のルンルン数を求める
    cin >> k;

    queue<long long int> runrun; //ルンルン数を入れる
    for(int i=1; i<=9; i++) runrun.push(i); //１〜９を挿入

    /* ルンルン数を１つずつ求める */
    for(int i=0; i<k-1; i++){
        long long int first = runrun.front(); //queueの先頭の要素を代入
        runrun.pop(); //先頭の要素を削除

        if(first % 10 != 0){
            runrun.push(first*10 + (first%10) - 1);
        }

        runrun.push(first*10 + (first%10));

        if(first % 10 != 9){
            runrun.push(first*10 + (first%10) + 1);
        }

    }

    cout << runrun.front() << endl;
}

Measured memory_bytes: 1792
/*
    ##############################
    #  Author: Pratyush Gaurav   #
    #  College: NIT ROURKELA     #
    ##############################
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli > plli;
typedef vector<lli> vlli;
typedef vector<plli > vplli;

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a * b) / gcd(a, b))
#define sqr(x) (x)*(x)
#define all(a) a.begin(),a.end()
#define UN(v) sort(all(v)), v.resize(unique(all(v))-v.begin())

#define endl '\n'

const long long INF = 100000000000000000;
const long long MOD = 1000000007;
const long long MAXN = 100005;

lli dx[]={0,0,-1,1,-1,-1,1,1};
lli dy[]={1,-1,0,0,1,-1,-1,1};

void solve() {
    lli n, k, sum = 0;
    cin >> n;
    vlli v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(all(v));
    sum = accumulate(all(v), 0ll);
    sum = sum - v[n - 1] + (v[n - 1] / 2);
    cout << sum << endl;
}

int main()
{
    IOS;
    lli t = 1;
    //cin >> t;

    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final char[] cubes = scanner.nextLine().toCharArray();

        int zeroCounter = 0;
        int oneCounter = 0;
        for (final char cube : cubes) {
            if (cube == '1') {
                oneCounter++;
            } else {
                zeroCounter++;
            }
        }

        System.out.println(2 * Math.min(zeroCounter, oneCounter));
    }
}


Measured memory_bytes: 26188
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def r_sort(a) a.sort{|a,b|b<=>a} end

n =inp[0]
a = [0]+inp
t = na(n+1,0)
ft = na(n+1,false)
ans = []
((n/2+1)..n).each do |i|
  ft[i] = true
  if(1 == a[i])
    t[i] = 1
    ans.push(i)
  end
end
(1..(n/2)).reverse_each do |i|
  d = i*(n/i)
  d += i
  c = 0
  while d > i
    d -= i
    c += t[d]
    next if(ft[d])
    ft[d] = true
    if(c % 2 != a[i])
      t[i] = 1
      ans.push(i)
    end
  end
end
puts ans.size
puts ans.join(" ") if(ans.size > 0)

Measured memory_bytes: 26324
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a*b, c*d) << endl;
    return 0;
}

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

int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	puts((a * b) & 1 ? "Yes" : "No");
        return 0;
}


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

using namespace std;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

struct edge{
	int from, to;
	edge(int from, int to):from(from), to(to){}
};
using node = vector<edge>;
using graph = vector<node>;
void addedge(graph &g, int from, int to, bool bidirectional = false){
	g[from].emplace_back(edge(from, to));
	if(bidirectional)g[to].emplace_back(edge(to, from));
}

class Solution {
public:
	void No(){
		cout << -1 << endl;
		return;
	}

	void solve() {
		int n, m;
		cin >> n >> m;
		vector<int> d(n);
		vector<pair<int,int>> di(n);
		for(int i=0; i<n; i++)cin >> d[i];
		for(int i=0; i < n; i++)di[i] = make_pair(d[i], i);
		sort(di.begin(), di.end());
		if(di[0].first != di[1].first)return No();
		vector<int> color(n, -1);
		map<pair<int, int>, int> etoi;
		graph g(n);
		for(int i=0; i < m; i++){
			int u, v;
			cin >> u >> v;
			u--, v--;
			etoi[make_pair(u, v)] = i;
			etoi[make_pair(v, u)] = i;
			addedge(g, u, v, true);
		}
		vector<int> w(m, 1000000000);
		for(int i=0; i < n; i++){
			int u = di[i].second;
			int x = di[i].first;
			if(color[u] != -1)continue;
			for(auto e:g[u]){
				if(color[e.to] != -1){
					color[u] = 1-color[e.to];
					w[etoi[make_pair(u, e.to)]] = x;
					break;
				}
				else if(d[u] == d[e.to]){
					color[u] = 0;
					color[e.to] = 1;
					w[etoi[make_pair(u, e.to)]] = x;
					break;					
				}
			}
			if(color[u] == -1)return No();
		}
		for(int i=0; i < n; i++){
			if(color[i])cout << "B";
			else cout << "W";
		}
		cout << "\n";
		for(int i=0; i<m; i++)cout << w[i] << " ";
		cout << "\n";
		
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 37760
#include<iostream>
#include<limits.h>
#include<algorithm>
#include<deque>
using namespace std;
const int INT = numeric_limits<int>::max();
int D[100005], k, f[100005], ok;
deque<int> q;
int main(){
    cin >> k;
    fill( D, D + k, INT );
    D[0] = 0;
    f[0] = 1;
    q.push_back( 0 );
    while( !q.empty() ){
        int x = q.front();
        q.pop_front();
        int x1 = (x + 1) % k;
        int x2 = (x * 10) % k;
        if( D[x1] > D[x] + 1 ){
            D[x1] = D[x] + 1;
            if( f[x1] == 0 )
                f[x1] = 1, q.push_back( x1 );
        }
        if( D[x2] > D[x] ){
            D[x2] = D[x];
            if( f[x2] == 0 )
                f[x2] = 1, q.push_front( x2 );
        }
        if( ok == 0 && x == 0 ){
            D[0] = INT;
            ok = 1;
        }
        f[x] = 0;
    }
    cout << D[0] << "\n";
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

vint to[1005], rto[1005];
vbool from_1(1005, false), to_n(1005, false);

struct edge {
    int to;
    int from;
    ll w;
};

void dfs(int v) {
    if (from_1[v]) return;
    from_1[v] = true;
    for (int u : to[v]) dfs(u);
}

void rdfs(int v) {
    if (to_n[v]) return;
    to_n[v] = true;
    for (int u : rto[v]) rdfs(u);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<edge> e(m);
    rep(i, m) {
        cin >> e[i].from >> e[i].to >> e[i].w;
        e[i].from--;
        e[i].to--;
        e[i].w *= -1;
        to[e[i].from].push_back(e[i].to);
        rto[e[i].to].push_back(e[i].from);
    }

    dfs(0);
    rdfs(n-1);
    vbool ok(n);
    rep(i, n) {
        ok[i] = from_1[i] & to_n[i];
    }

    vll v(n, LINF);
    v[0] = 0;
    rep(i, n) {
        bool update = false;
        rep(j, m) {
            if (ok[e[j].from] == false && ok[e[j].to] == false) continue;
            if (v[e[j].to] > v[e[j].from] + e[j].w) {
                v[e[j].to] = v[e[j].from] + e[j].w;
                update = true;
            }
        }
        if (i == n-1 && update) {
            puts("inf");
            return 0;
        }
    }
    ll ans = v[n-1] * -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//vector<pair<ll,ll>> pc;
//int ABS(int a){return max(a,-a);}
//int a[100001];
int main(){
   int a,b,c,ans;
    cin>>a>>b>>c;
    ans=b/a;
    if(ans>c) cout<<c;
    else cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};



signed main(){
  int a,b,c;cin>>a>>b>>c;
  int ans=min({a+b,b+c,c+a});
  cout<<ans<<"\n";

  return 0;
}


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

using namespace std ;

const int N = 1e5 + 10 ;
int n , a[N] ;




int main(){
    scanf("%d" , &n) ;
    for(int i = 0 ; i < n ; i++)
        scanf("%d" , &a[i]) ;


    int res[n + 10] ;
    res[0] = 0 ; res[1] = abs(a[1] - a[0]) ;
    for(int i = 2 ; i < n ; i++)
        res[i] = min(res[i - 1] + abs(a[i] - a[i - 1]) , res[i - 2] + abs(a[i] - a[i - 2]) ) ;


    printf("%d\n" , res[n - 1]) ;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 1000000007
#define ll long long
using namespace std;
ll ls[114514],rs[114514];
signed main(){
	int n;
	cin>>n;
	vector<ll> l,r;
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		l.pb(2*x);r.pb(-2*y);
	}
	sort(l.begin(),l.end(),greater<ll>());
	sort(r.begin(),r.end(),greater<ll>());
	ls[0] = l[0];rs[0]=r[0];
	for(int i=1;i<n;i++){
		ls[i] = ls[i-1] + l[i];
		rs[i] = rs[i-1] + r[i];
	}
	ll ans = 0;
	for(int i=0;i<=n;i++){
		ll tmp;
		if(i%2==0){
			tmp = ls[i/2-1]+rs[i/2-1];
		}
		else{
			tmp =  max(ls[i/2]+rs[i/2-1], ls[i/2-1]+rs[i/2]);
		}
		ans = max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

#define ll long long
#define ld long double

signed main() {
	cout << setprecision(20);
	int n; cin >> n;
	vector<int> t(n), a(n);
	for (int i = 0; i < n; ++i)
		cin >> t[i] >> a[i];
	// パフォーマンスの累積をとる
	vector<ld> acc_perf(n + 1);
	acc_perf[0] = 1.0;
	for (int i = 1; i <= n; ++i)
		acc_perf[i] = acc_perf[i - 1] * ((ld)10 - a[i - 1]) / 10;
	// クエリに答える
	t.push_back(1000000001);
	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		int il = lower_bound(t.begin(), t.end(), l) - t.begin();
		int ir = upper_bound(t.begin(), t.end(), r) - t.begin();
		ld rt = acc_perf[ir] / acc_perf[il];
		cout << (1e9 * rt) << endl;
	}
	return 0;
}


Measured memory_bytes: 5520
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int a[600][600];
void solve(int l , int r, int x){
    if(l+1==r)return;
    int m = (l+r)/2;
    REP(i,l,m)REP(j,m,r){
        a[i][j]=x;
    }
    solve(l,m,x+1);
    solve(m,r,x+1);
}

int main(){
    int n;
    cin>>n;
    solve(0,n,1);
    rep(i,n){
        REP(j,i+1,n)cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1664
function Scanner(input) {
	var self = this;
	self.itemNo = 0;
	self.orgStr = input;
	self.splitedStrs = (function(target) {
		var result = [];
		var target = target.replace(/[\n \t]+/g, " ");
		var strs = target.split(" ");
		for (var i = 0, len = strs.length; i < len; i++) {
			result.push(strs[i]);
		}
		return result;
	}(input));

	self.next = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? result : null;
	}

	self.nextInt = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseInt(result) : null;
	}

	self.nextBigDecimal = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? parseFloat(result) : null;
	}
	
	self.nextByte = function() {
		var result = self.splitedStrs[self.itemNo];
		self.itemNo++;
		return (result != null) ? new Int8Array(result) : null;
	}

}

function Main(sc) {

	var S = sc.next();
	var T = sc.next();
	
	var ans = false;
	
	ans = T.indexOf(S) == 0 && S.length + 1 == T.length
	
	console.log(ans ? "Yes" : "No");
}
Main(new Scanner(require("fs").readFileSync("/dev/stdin", "utf8")));
// Main(new Scanner("10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10"));

// var str1 = sc.next(); // Stringで取得
// var int1 = sc.nextInt(); // intで取得
// var bd1 = sc.nextBigDecimal(); // BigDecimalで取得
// var byte1 = sc.nextByte(); // byteで取得
// for (var i = 0; i < 1000000000; i++) var toDelay = "aaa"; // 1000msくらいの遅延
// console.log(wrtnNos); return;


Measured memory_bytes: 29640
from math import factorial


def comb(a, b):
    if b < 0 or a < b:
        return 0
    return factorial(a) // factorial(b) // factorial(a - b)


N, A, B = map(int, input().split())
V = [int(s) for s in input().split()]
V.sort(reverse=True)
ans1 = sum(V[:A]) / A
num = V.count(V[A - 1])
if V[0] == V[A - 1]:
    ans2 = sum([comb(num, m) for m in range(A, B + 1)])
else:
    m = V[:A].count(V[A - 1])
    ans2 = comb(num, m)
print(ans1)
print(ans2)


Measured memory_bytes: 3064
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
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(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class AServalVsMonster {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int h, a; cin >> h >> a;
      cout << (h+a-1)/a << endl;

    }
};

signed main() {
  AServalVsMonster solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 256
n, a, b, c, d = gets.chomp.split.map(&:to_i)
s = gets.chomp
  (b-1).upto(d-2) do |i|
    if s[i] == "#" && s[i+1] == "#"
      puts "No"
      exit
    end
  end
  (a-1).upto(c-2) do |i|
    if s[i] == "#" && s[i+1] == "#"
      puts "No"
      exit
    end
  end
if c < d
  puts "Yes"
elsif d < c
  (b-2).upto(d-2) do |i|
    if s[i] == "." && s[i+1] == "." && s[i+2] == "."
      puts "Yes"
      exit
    end
  end
  puts "No"
end


Measured memory_bytes: 2172
import java.util.*;

public class Main {

    long INF = Long.MAX_VALUE;
    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N =sc.nextInt();
        int[] H = new int[N];
        int Hmax = 0;
        int c = 0;
        for(int i = 0;i < N;i++){
            H[i] = sc.nextInt();
            if(Hmax <= H[i]){
                Hmax = H[i];
                c++;
            }
        }
        System.out.println(c);
    }
}


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

int main() {
  int N,s=0;
  cin>>N;
  int M=N;
  for(int i=0;i<10;i++){
    s+=N%10;
    N=N/10;
  }
  if(M%s==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
    

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn= 4e5,maxm= 7e6;
struct node{
	int o,l,r;
};
node sta[10];
char s[maxn];
int c[maxn],f[maxn];
int left[maxm],right[maxm],S[maxm],Z[maxm],Min[maxm];
int n,m,i,x,y,z,tot,root,L,R,now,la;
//S[]当前子?是否有-1,Z[]区???,Min[]区?最小?
void init(){
	memset(s,0,sizeof(s));          
	memset(c,0,sizeof(c));
	memset(f,0,sizeof(f));
	memset(left,0,sizeof(left));
	memset(right,0,sizeof(right));
	memset(S,0,sizeof(S));
	memset(Z,0,sizeof(Z));
	memset(Min,0,sizeof(Min));
	L= 1;R= n+1;tot= root= 0;
}
void pushdown(int o){
	Z[left[o]]+= Z[o];
	Z[right[o]]+= Z[o];
	Z[o]= 0;
}
void update(int o){
	int l= left[o],r= right[o];
	S[o]= S[l]||S[r];
	Min[o]= min(Min[l]+Z[l],Min[r]+Z[r]);
}
void build(int &o,int l,int r){
	if (!o) o= ++tot;
	if (l+1==r){
		S[o]= c[l]==-1?1:0;
		Min[o]= f[l];
		return;
	}
	int mid= (l+r)>>1;
	build(left[o],l,mid);
	build(right[o],mid,r);	
	update(o);
}
void find(int o,int l,int r,int L,int R){
	if (l==r) return;
	if (l>=R) return;
	if (l+1==r){
		now= l;
		return;
	}
	pushdown(o);
	int mid= (l+r)>>1;
	if (S[left[o]]) find(left[o],l,mid,L,R);
	else find(right[o],mid,r,L,R);
	update(o);
}
void change(int o,int l,int r,int v,int x){
	if (l==r) return;
	if (l+1==r){
		S[o]= c[l]==-1?1:0;
		return;
	}
	pushdown(o);
	int mid= (l+r)>>1;
	if (v<mid) change(left[o],l,mid,v,x);
	else change(right[o],mid,r,v,x);
	update(o);
}
void modify(int o,int l,int r,int L,int R,int x){
	if (l==r) return;	
	if (L<=l&&r<=R){
		Z[o]+= x;
		return;
	}
	pushdown(o);
	int mid= (l+r)>>1;
	if (L<mid) modify(left[o],l,mid,L,R,x);
	if (mid<R) modify(right[o],mid,r,L,R,x);
	update(o);
}
void ask(int o,int l,int r,int L,int R){
	if (l==r) return;	
	if (L<=l&&r<=R){
		sta[++la]= (node){o,l,r};
		return;
	}
	pushdown(o);
	int mid= (l+r)>>1;
	if (L<mid) ask(left[o],l,mid,L,R);
	if (mid<R) ask(right[o],mid,r,L,R);
	update(o);
}
void go(int o,int l,int r){
	if (l==r) return;	
	if (l+1==r){
		if (Min[o]+Z[o]>=2)
			now= l;
		return;
	}
	pushdown(o);
	int mid= (l+r)>>1;
	if (Min[right[o]]+Z[right[o]]>=2){
		now= mid;
		go(left[o],l,mid);
	}else {
		go(right[o],mid,r);
	}update(o);
}
void Ask(int x){	
	la= 0;now= x;
	ask(root,L,R,1,x);
	while (la){
		int o= sta[la].o;
		if (Min[o]+Z[o]>=2){
			now= sta[la].l;
			la--;
		}else break;
	}
	go(sta[la].o,sta[la].l,sta[la].r);
}
int main()
{
	while (scanf("%d%d",&n, &m)>0){
		init();
		scanf("%s",s+1);
		for (i= 1;i<=n;i++){
			c[i]= s[i]=='(' ? 1:-1;
			f[i]= f[i-1]+c[i];
		}
		build(root,L,R);
		for (int MM= 1;MM<=m;MM++){
			scanf("%d",&x);
			now= x;
			if (c[x]==1){
				c[x]= -1;
				find(root,L,R,1,x);
				c[now]= 1;
				change(root,L,R,x,-1);
				change(root,L,R,now,1);
				modify(root,L,R,now,x,2);
			}else {
				c[x]= 1;
				Ask(x);
				c[now]= -1;
				change(root,L,R,x,1);
				change(root,L,R,now,-1);
				modify(root,L,R,now,x,-2);
			}
			printf("%d\n",now);
		}
	}return 0;
}

Measured memory_bytes: 141272
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a;
int n, K;
bool judge(int x)
{
    if(K-a[x] <= 0) return true;
    vector<vector<bool>> dp(5010, vector<bool>(5010));
    dp[0][0] = true;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= K; j++)
        {
            if(i == x)
            {
                dp[i][j] = dp[i][j] || dp[i-1][j];
            }
            else
            {
                dp[i][j] = dp[i][j] || dp[i-1][j];
                if(dp[i-1][j] && j + a[i] <= K)
                {
                    dp[i][j+a[i]] = true;
                }
            }
        }
    }
    bool flag = false;
    for(int i = K-a[x]; i <= K - 1; i++)
    {
        if(dp[n][i])
        {
            flag = true;
        }
    }
    return flag;
}
int main()
{
    cin >> n >> K;
    a.push_back(0);
    for(int i = 0; i < n; i++)
    {
        ll b;
        cin >> b;
        a.push_back(b);
    }
    sort(a.begin(), a.end());
    int lb = 0;
    int ub = n+1;
    while(ub - lb > 1)
    {
        int mid = (lb+ub) / 2;
        if(judge(mid))
        {
            ub = mid;
        }
        else
        {
            lb = mid;
        }
    }
    cout << lb << endl;
}



Measured memory_bytes: 3720
using System;
using System.Collections.Generic;

public class ABC162D {
	private static void Main(string[] args) {
		var n = ReadInt();
		var s = ReadStr();

		var dict = new Dictionary<char, long>() {
			{'R', 0}, {'G', 0}, {'B', 0}
		};

		for (var i = 0; i < n; i++) 
			dict[s[i]]++;

		var answer = dict['R'] * dict['G'] * dict['B'];

		for (var i = 0; i <= n; i++) {
			for (var dif = 1; (i + dif + dif) < n ; dif++) {
				var j = i + dif;
				var k = j + dif;

				if ((s[i] != s[j]) && (s[i] != s[k]) && (s[j] != s[k]))
					answer--;
			}
		}

		Console.WriteLine(answer);
	}

	private static string ReadStr() => Console.ReadLine().Trim();
	private static int ReadInt() => int.Parse(Console.ReadLine().Trim());
}

Measured memory_bytes: 27828
import java.util.Scanner;
import java.util.Random;
import java.util.Arrays;

class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int sum = a + b;
		
		if (a%3 == 0 || b%3 ==0 || sum%3 == 0) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}
		
	}
}

Measured memory_bytes: 23764
<?php
    fscanf(STDIN, "%s", $s);
    $result = '';
    if($s == 'Sunny'){
        $result = 'Cloudy';
    }else if($s == 'Cloudy'){
        $result =  'Rainy';
    }else if($s == 'Rainy'){
        $result = 'Sunny';
    }
    echo $result;
  ?>

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  string S;
  cin >> S;
  int N = S.size() - 1;
  ll sum = 0;
  for (int i = 0; i < (1 << N); i++)
  {
    ll tmp = 0;
    int l = 0, r;
    for (r = 0; r < N; r++)
    {
      if (i & (1 << r))
      {
        string t = S.substr(l, r - l + 1);
        ll num = stoll(t);
        tmp += num;
        l = r + 1;
      }
    }
    string t = S.substr(l, r - l + 1);
    ll num = stoll(t);
    tmp += num;
    sum += tmp;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
c = [list(input()) for _ in range(h)]

ans = [[''] * w for _ in range(2 * h)]

for i in range(2 * h):
    for j in range(w):
        ans[i][j] = c[i // 2][j]

for line in ans:
    print(''.join(line))


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long 
#define FF first
#define SS second
#define MOD 1000000007

using namespace std;

int gcd(int a, int b) {
  while (a > 0 && b > 0)
    if (a > b) a %= b;
    else b %= a;
  return a + b;
}

ll modpower(ll x, ll y, ll p) //x^y mod p
{
    ll res = 1;      // Initialize result
 
    x = x % p;  // Update x if it is more than or 
                // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y %2!= 0)
            res = (res*x) % p;
 
        // y must be even now
        y = y/2;
        x = (x*x) % p;  
    }
    return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int n,c;
	cin>>n>>c;
	ll d[c][c];
	for(int i=0;i<c;i++)
	{
		for(int j=0;j<c;j++)
		{
			cin>>d[i][j];
		}
	}
	ll init[n][n];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>init[i][j];
			init[i][j]--;
		}
	}
	ll arr[31][3];
	for(int i=0;i<31;i++)for(int j=0;j<3;j++)arr[i][j]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int m = (i+j)%3;
			for(int k=0;k<c;k++)
			{
				arr[k][m]+=d[init[i][j]][k];
			}
		}
	}
	ll ans = 100000000000000000;
	for(int i=0;i<c;i++)
	{
		for(int j=0;j<c;j++)
		{
			for(int k =0;k<c;k++)
			{
				if(i!=j && j!=k && k!=i)
				{
					ll kx = arr[i][0] + arr[j][1] + arr[k][2];
					if(kx<ans)
					{
						ans = kx;
					}
				}
			}
		}
	}
	cout<<ans;


}


Measured memory_bytes: 2176
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func main() {
	scanner.Split(bufio.ScanWords)

	w := nextInt()
	n := nextInt()

	numbers := make([]int, w+1)
	for i := 1; i <= w; i++ {
		numbers[i] = i
	}

	for i := 0; i < n; i++ {
		line := nextString()
		words := strings.Split(line, ",")
		a, _ := strconv.Atoi(words[0])
		b, _ := strconv.Atoi(words[1])

		numbers[a], numbers[b] = numbers[b], numbers[a]
	}

	for i := 1; i <= w; i++ {
		fmt.Println(numbers[i])
	}
}



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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

int n;
// string s;
Vi h;

int f(int s, int e, int x) {
    if (s > e) return 0;
    int mini = *min_element(h.begin() + s, h.begin() + e+1);
    int sum = mini - x;
    int y = s;
    REP2(i, s, e+1) {
        if (h[i] == mini) {
            sum += f(y, i-1, mini);
            y = i+1;
        }
    }
    if (y != e+1) {
        sum += f(y, e, mini);
    }
    return sum;
}

int main() {
    cin >> n;
    h = Vi(n);
    REP(i, n) cin >> h[i];

    cout << f(0, n-1, 0) << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
ll arr[maxn], n;

ll getsum(ll b) {
    ll sum = 0LL;
    for(int i=1;i<=n;i++) {
        sum += abs(arr[i] - (b+i));
    }
    return sum;
}

ll bin_search() {
    ll index = -INT_MAX;
    for(ll cekor = INT_MAX/2; cekor > 0; cekor /= 2) {
        while(index < LLONG_MAX - cekor && getsum(index+cekor) > getsum(index+cekor+1)) index+=cekor;
    }
    return index;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
    }
    ll x = bin_search();
    cout<<getsum(x+1)<<"\n";
    return 0;
}


Measured memory_bytes: 1792
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val Array(s, t) = sc.nextLine().split(" ")
    val A, B = sc.nextInt(); sc.nextLine()
    val u = sc.nextLine()

    if (u == s) println(s"${A-1} ${B}")
    else println(s"$A ${B-1}")
  }

}


Measured memory_bytes: 26056
#include<stdio.h>
#include<math.h>

int main (void)
{
	int kazu;
	double x[100],y[100];
	int a;
	double an1=0,at1,an2,at2=0,an3,at3,az3,go3=0,anm,sa[100];
	

	scanf("%d",&kazu);

	for(a=0;a<100;a++)//?????????
	{
		x[a]=0;
		y[a]=0;
		sa[a]=0;
	}

	for(a=0;a<kazu;a++)//x?????\???
	{
		scanf("%lf",&x[a]);
	}
	for(a=0;a<kazu;a++)//y?????\???
	{
		scanf("%lf",&y[a]);
	}
	

	for(a=0;a<kazu;a++)//??????????????????
	{
		at1= x[a]-y[a];
		if(at1<0)
		{
			at1=-1*at1;
		}

		an1= an1 + at1;
		
	}

	for(a=0;a<kazu;a++)//??????????????????
	{
		at2=(x[a]-y[a])*(x[a]-y[a])+at2;
		an2=sqrt(at2);
	}

	for(a=0;a<kazu;a++)//??????????????????
	{
		at3=x[a] - y[a];
		if(at3 < 0)
		{
			at3 = -1*at3;
		}

		az3=pow(at3,3);
		go3=go3+az3;
	}
		an3=pow(go3,1.0/3.0);


	 
	for(a=0;a<kazu;a++)//???????????????
	{
		sa[a]=x[a]-y[a];
		
		if(sa[a]<0)
		{
			sa[a]=-1*sa[a];
		}
		
	}
		
	anm = sa[0];
	for(a=0;a<kazu;a++)
	{
		
		if(anm<sa[a])
		{
			anm=sa[a];
		}
		else
		{
			anm = anm;
		}

	}
	
	printf("%f %f %f %f\n",an1,an2,an3,anm);

	return 0;
}

Measured memory_bytes: 720
# c
M = 10**9+7
n = int(input())
s = input()
if (s[0] != 'B') | (s[-1] != 'B'): print(0); exit()
a = [1]+[0]*(2*n-1)
b = [0]*2*n
for i in range(1, 2*n):
    if s[i] == s[i-1]:
        a[i] = 1^a[i-1]
        b[i] = 1^b[i-1]
    else:
        a[i] = a[i-1]
        b[i] = b[i-1]
if (sum(a) != sum(b)) | (b[-1] == 0):
    print(0); exit()
for i in range(1, 2*n):
    a[i] += a[i-1]-b[i]
c = 1
for i, j in zip(a, b[1:]):
    if j: c *= i*j; c %= M
for i in range(1, n+1):
    c = c*i%M
print(c)

Measured memory_bytes: 45636
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define repp(i,n) for(int (i) = 1; (i) <= (n); ++(i))
#define popcnt __builtin_popcount
#define all(v) v.begin(),v.end()
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
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;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}

int main(){
    int n; cin >> n;
    int ans = 0;

    for(int i = 1; i <= n ; i += 2){
        int divisors = 0;
        for(int j = 1; j <= i; ++j){
            if(i % j == 0) ++divisors;
        }
        if(divisors == 8) ++ans;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define rrep(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = int(s); i < int(n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==int(v.size()-1)?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,q;
    cin >> n >> q;
    vi a(n);
    cin >> a;
    vl sr(n),sl(n);
    sr[n-1] = a[n-1];
    rrep(i,n-1) sr[i] = sr[i+1]+a[i];
    rep(i,n) {
        sl[i] = a[i];
        if(i >= 2) sl[i] += sl[i-2];
    }
    while(q--) {
        int x;
        cin >> x;
        if(x >= a[n-1]) {
            cout << sl[n-1] << '\n';
            continue;
        }
        auto it = lower_bound(all(a),x);
        int ok = n-1,ng = (it-a.begin()-1);
        auto f = [&](int now) {
            auto l = lower_bound(all(a),x*2-a[now]);
            return now-(l-a.begin())+1 >= n-now;
        };
        while(abs(ok-ng) > 1) {
            int mid = (ng+ok)/2;
            if(f(mid)) ok = mid;
            else ng = mid;
        }
        ll ans = sr[ok];
        if(ok-(n-ok)-1 >= 0) ans += sl[ok-(n-ok)-1];
        cout << ans << '\n';
    }
}

Measured memory_bytes: 5280
#include<bits/stdc++.h>
using namespace std;
#include <math.h>
#define ll long long 
// to increase precision
// std::cout<<std::fixed;
// 	std::cout<<std::setprecision(6)<<z;
#define max1 1000001

//long long int mod=1e18 ;


int main(){	
	int n,k;
	cin>>n>>k;
	vector<int> h(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>h[i];
	}
	int dp[n+1]={0};
	dp[1]=0;
	//dp[2]=abs(h[1]-h[0]);
	for (int i = 2; i <=n; ++i)
	{
		dp[i]=1e9;
		for(int j=i-1;j>=max(1,i-k);j--){
			dp[i]=min(dp[i],dp[j]+abs(h[i-1]-h[j-1]));
		}
	}
	cout<<dp[n]<<endl;


}
	
	
	
	





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

int n;
int a[2000];
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a, a + n);
  
  long sum = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int r = lower_bound(a, a + n, a[i] + a[j]) - a;
      sum += r - j - 1;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
n = int(input())
name = []
time = []
for _ in range(n):
    s, t = input().split()
    t = int(t)
    name.append(s)
    time.append(t)
x = input()
total = 0
ind = name.index(x)
for index, t in enumerate(time):
    if index <= ind:
        continue
    total += t
print(total)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
char s[1000005];
vector<pii> v1, v2;
int main(){
    int n, tot = 0;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%s", s+1);
        int l = strlen(s+1);
        int sum = 0, mn = 0;
        for(int j=1;j<=l;j++){
            if(s[j] == '(') sum++;
            else sum--;
            mn = min(mn, sum);
        }
        tot += sum;
        if(sum >= 0) v1.emplace_back(pii(-mn, sum));
        else{
            sum = 0, mn = 0;
            for(int j=l;j>=1;j--){
                if(s[j] == ')') sum++;
                else sum--;
                mn = min(mn, sum);
            }
            v2.emplace_back(pii(-mn, sum));
        }
    }
    if(tot != 0){
        printf("No\n");
        return 0;
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    int cur = 0;
    for(int i=0;i<v1.size();i++){
        int mn = v1[i].first, sum = v1[i].second;
        if(cur < mn){
            printf("No\n");
            return 0;
        }
        cur += sum;
    }

    cur = 0;
    for(int i=0;i<v2.size();i++){
        int mn = v2[i].first, sum = v2[i].second;
        if(cur < mn){
            printf("No\n");
            return 0;
        }
        cur += sum;
    }
    printf("Yes\n");
}

Measured memory_bytes: 11368
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main(){
    int n0, n1, n2, ans;
    cin >> n0 >> n1 >> n2;
    ans = n0*100 + n1*10 + n2;
    if(ans%4 == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;

// B - Maximum Sum
int main(){
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    for(int i=0;i<K;++i){
        if(A>=B && A>=C){
            A*=2;
        }else if(B>=A && B>=C){
            B*=2;
        }else{
            C*=2;
        }
    }
    int ans = A + B + C;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256