akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 文字列
		int ac = 0;
		int wa = 0;
		int tle = 0;
		int re = 0;
		
		for (int i = 0; i < n; i++) {
			String str = sc.next();
			
			switch(str) {
				case "AC" :
					ac++;
					break;
					
				case "WA" :
					wa++;
					break;
					
				case "TLE" :
					tle++;
					break;
					
				case "RE" :
					re++;
					break;
			}
		}

		System.out.println("AC x " + ac);
		System.out.println("WA x " + wa);
		System.out.println("TLE x " + tle);
		System.out.println("RE x " + re);
	}
}

Measured memory_bytes: 58776
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Main m = new Main(sc);
        m.show(m.solve());
    }
    
    Scanner sc;
    int N;
    int[] answer;   //条件を満たす個数のカウント
    
    //入力
    Main(Scanner sc) {
        this.sc = sc;
        N = sc.nextInt();
        answer = new int[N];
    }
    
    //解答処理
    int[] solve() {
        for (int x=1; x<100; ++x){
            for (int y=1; y<100; ++y){
                for (int z=1;z<100; ++z){
                    int n = x*x + y*y + z*z + x*y + y*z + z*x;
                    if (n <= N){
                        ++answer[n-1];
                    }
                }
            }
        }
        
        return answer;
    }
    
    //出力
    void show(int[] answer) {
        for (int i=0; i<N; ++i){
            System.out.println(answer[i]);
        }
    }
}

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

require 'prime'

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 sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

def bi(x)
  return 1 if(x == 1)
  return bi(x/2) * 2 + 1
end
puts bi(inp[0])

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

int main() {
  int n,r;
  cin >>n;
  vector<int> c(n),v(n);
  r=0;
  for(int i=0;i<n;i++){
       cin >> v.at(i);
	   
  }
  
  for(int i=0;i<n;i++){
       cin >> c.at(i);
	   
  }
  
  for(int i=0;i<n;i++){
       if(v.at(i)>c.at(i)) r+=v.at(i)-c.at(i);
	   
  }
  
  
  cout << r << endl;
}


Measured memory_bytes: 256
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;

//#[proconio::fastout]
fn main() {
    input! {
        s: Bytes,
    }

    let b = s[0] == b'7' || s[1] == b'7' || s[2] == b'7';
    println!("{}", if b { "Yes" } else { "No" });
}


Measured memory_bytes: 2100
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
#include <set>
#include <iomanip>
using namespace std;
 
 
int main(){
    int N, X;
    cin >> N;
    X = N / 1.08;
    if (int(X * 1.08) == N){
        cout << X << endl;
    }else if(int((X+1) * 1.08) == N){
        cout << X + 1 << endl;
    }else{
        cout << ":(" << endl;
    }
    return 0;
}

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

template <class T>
struct BIT{
	int n;
	vector<T> x;
	BIT(int n_ = 0) : n(n_), x(n + 1, 0){}
	int size() const{ return n; }
	T sum(int r) const{
		T S = 0;
		for(r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
		return S;
	}
	T sum(int l, int r) const{ return sum(r) - sum(l); }
	void add(int k, const T &a){
		for(; k < n; k |= k + 1) x[k] += a;
	}
	void set(int k, const T &a){ add(k, a - sum(k, k + 1)); }
	int lower_bound(T x){
		int ng = -1, ok = n - 1;
		while(abs(ng - ok) > 1){
			int mid = (ng + ok) / 2;
			if(sum(0, mid + 1) >= x) ok = mid;
			else ng = mid;
		}
		return ok;
	}
};

const int MAX_N = 1000000;
BIT<ll> bit(MAX_N);

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int n;
	cin >> n;

	set<int> s;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;

		bool yes = false;
		if(s.count(0)){
			yes = false;
		}
		else if(s.count(x) == 0){
			s.insert(x);
			if(x < MAX_N) bit.add(x, 1);
			yes = true;
		}
		else{
			if(x < MAX_N && bit.sum(1, x) == x - 1 && s.upper_bound(x) != s.end()){
				yes = false;
			}
			else{
				yes = true;
				// ??£???
				while(s.count(x)){
					s.erase(x);
					if(x < MAX_N) bit.add(x, -1);
					x--;
				}
				s.insert(x);
				if(x < MAX_N) bit.add(x, 1);
			}
		}
		if(yes) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

Measured memory_bytes: 22388
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 998244353;
const int MAXN =(int) 2e5+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
int a,b;

void work(){
    scanf("%d%d",&a,&b);
    if(1<=a&&a<=9&&1<=b&&b<=9){
        printf("%d\n",a*b);
    }
    else{
        printf("-1\n");
    }
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}





Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;

    int ans = 1e9;
    for (int i = 0; i <= N/6; i++) {
        int K = N - 6*i, cnt = 0, j = i;
        while (j > 0) {
            cnt += j%6;
            j /= 6;
        }
        while (K > 0) {
            cnt += K%9;
            K /= 9;
        }
        chmin(ans,cnt);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
n,k = map(int,input().split())
arr = list(map(int,input().split()))

dp = [False]*(k+1)

for stones in range(k+1):
    for x in arr:
        if stones >= x and dp[stones-x] == False:
            dp[stones] = True

if dp[k]:
    print("First")
else:
    print("Second")


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

int main()
{
  string S, T;
  cin >> S >> T;
  bool can = false;
  for (int i = 0; i < S.size(); i++)
  {
    char tmp = S[S.size() - 1];
    for (int j = S.size() - 1; j >= 1; j--)
    {
      S[j] = S[j - 1];
    }
    S[0] = tmp;
    if (S == T)
    {
      can = true;
      break;
    }
  }
  if (can)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


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

int main(int argc, char *argv[]) {
  int H, W;
  cin >> H >> W;
  int a[H][W];
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      cin >> a[i][j];
    }
  }
  vector<string> v;
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(a[i][j] % 2 == 1) {
        if(i == H-1 && j == W-1) continue;
        if(j == W-1) {
          a[i][j]--;
          a[i+1][j]++;
          v.push_back(to_string(i+1) + " " + to_string(j+1) + " " + to_string(i+2) + " " + to_string(j+1));
          continue;
        }
        if(i == H-1) {
          a[i][j]--;
          a[i][j+1]++;
          v.push_back(to_string(i+1) + " " + to_string(j+1) + " " + to_string(i+1) + " " + to_string(j+2));
          continue;
        }
        if(a[i][j+1] % 2 == 1) {
          a[i][j]--;
          a[i][j+1]++;
          v.push_back(to_string(i+1) + " " + to_string(j+1) + " " + to_string(i+1) + " " + to_string(j+2));
        } else {
          a[i][j]--;
          a[i+1][j]++;
          v.push_back(to_string(i+1) + " " + to_string(j+1) + " " + to_string(i+2) + " " + to_string(j+1));
        }
      }
    }
  }
  cout << v.size() << endl;
  for(int i = 0; i < v.size(); i++) {
    cout << v[i] << endl;
  }
  return 0;
}


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

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

int main(){
    int s, w; cin >> s >> w;
    if (s > w) cout << "safe" << endl;
    else cout << "unsafe" << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int n;
int x;
int i;
void CHECK_NUM();
void INCLUDE3();
void END_CHECK_NUM();
int main(){
  cin >> n;
  i=1;
  CHECK_NUM();
}
void CHECK_NUM(){
  x = i;
  if(x%3==0){
    cout << " " << i;
    END_CHECK_NUM();
  }else{
    INCLUDE3();
  }
}
void INCLUDE3(){
  if(x%10 == 3){
    cout << " " <<i;
    END_CHECK_NUM();
  }else{
    x/=10;
    if(x){
      INCLUDE3();
    }
    else{
      END_CHECK_NUM();
    }
  }
}
void END_CHECK_NUM(){
  if(++i<=n){
    CHECK_NUM();
  }else{
    cout << endl;
  }
}

Measured memory_bytes: 3072
#include <iostream>
#include <bitset>
#define ll long long
using namespace std;
const int MDSZ = 1;
const int MD[4] = {1000000007, 1069696919, 701, 1018199999};
int n, k, ar[5001] = {}, rs = 0, a = 0, b = 0;
int dp[5001][MDSZ] = {};
void outDP(string s)
{
	cout << s << " : \n";
	for (int i = 0; i < k; i++)
	{
		cout << i << " " << dp[i][0] << "\n";
	}
}
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k; rs = n;
	for (int i = 0; i < n; i++) 
	{
		cin >> ar[i];
		if (ar[i] >= k) {a++;}
	}
	rs -= a;
	for (int i = 0; i < MDSZ; i++) {dp[0][i] = 1;}
	for (int i = 1; i <= n; i++)
	{
		for (int j = k - 1; j >= ar[i - 1]; j--) 
		{
			for (int kk = 0; kk < MDSZ; kk++)
			{
				dp[j][kk] += dp[j - ar[i - 1]][kk];
				dp[j][kk] %= MD[kk];
			}
		}
	}
	//outDP("ALL");
	for (int i = 1; i <= n; i++)
	{
		if (ar[i - 1] < k)
		{
			for (int j = ar[i - 1]; j < k; j++)
			{
				for (int kk = 0; kk < MDSZ; kk++)
				{
					dp[j][kk] -= dp[j - ar[i - 1]][kk];
					dp[j][kk] %= MD[kk];
					dp[j][kk] = (dp[j][kk] + MD[kk]) % MD[kk];
				}
			}
			//outDP("REM" + to_string(i));
			for (int j = k - ar[i - 1]; j < k; j++)
			{
				bool ck = 1;
				for (int kk = 0; kk < MDSZ; kk++) {ck &= (dp[j][kk] > 0);}
				if (ck) {rs--; break;}
			}
			for (int j = k - 1; j >= ar[i - 1]; j--) 
			{
				for (int kk = 0; kk < MDSZ; kk++)
				{
					dp[j][kk] += dp[j - ar[i - 1]][kk];
					dp[j][kk] %= MD[kk];
				}
			}
			//outDP("FIX" + to_string(i));
		}
	}
	cout << rs << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
int main()
{
    IOS
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     // freopen("error.txt","w",stderr);
      char c;
      cin>>c;
      if('A'<=c && c<='Z')
      {
        cout<<'A'<<endl;
      }  
      else
      {
        cout<<'a'<<endl;
      }
    return 0;
}

Measured memory_bytes: 3568
N=int(input())
#f=nf(n-2)

count=0
if N%2==1:
    print(0)
else:
    count+=N//10
    #print(count)
    N//=10
    while N>=5:
        count+=N//5
        #print(count)
        N//=5
    print(count)
#
"""
def f(n):
    if n>=2:
        answer=n
        n-=2
    while n>=2:
        answer*=n
        n-=2
    return answer
print(f(N))
"""
    

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

int calc_sum_digits(int x) {
  int sum = 0;
  do {
    sum += x % 10;
    x /= 10;
  } while (x != 0);
  return sum;
}

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  int sum_d = 0;
  for (int i = 1; i <= n; ++i) {
    int num = calc_sum_digits(i);
    if (a <= num && num <= b) {
      sum_d += i;
    }
  }
  cout << sum_d << endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <climits>
#include <cmath>
#include <cfloat>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define CLR(mat) memset(mat, 0, sizeof(mat))

using namespace std;

int n, m;
vector<int> veg;

int solve()
{
	int res = 0;
	sort(veg.rbegin(), veg.rend());
	
	FOR(i, 0 ,n)
	{
		if( (i+1)%m != 0 )
		{
			res += veg[i];
		}
	}
	
	return res;
}

int main()
{
	while( cin >> n >> m, (n||m))
	{
		veg.clear();
		
		FOR(i,0,n)
		{
			int a;
			cin >> a;
			veg.push_back(a);
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node { int parent, left, right; };

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d) {
  if ( u == NIL ) return;
  D[u] = d;
  setDepth(T[u].left, d + 1);
  setDepth(T[u].right, d + 1);
}

int setHeight(int u) {
  int h1 = 0, h2 = 0;
  if ( T[u].left != NIL )
    h1 = setHeight(T[u].left) + 1;
  if ( T[u].right != NIL )
    h2 = setHeight(T[u].right) + 1;
  return H[u] = ( h1 > h2 ? h1 : h2);
}

// 節点 u の兄弟を返す
int getSibling(int u) {
  if ( T[u].parent == NIL ) return NIL;
  if ( T[T[u].parent].left != u && T[T[u].parent].left != NIL )
    return T[T[u].parent].left;
  if ( T[T[u].parent].right != u && T[T[u].parent].right != NIL )
    return T[T[u].parent].right;
  return NIL;
}

void print(int u) {
  printf("node %d: ", u);
  printf("parent = %d, ", T[u].parent);
  printf("sibling = %d, ", getSibling(u));
  int deg = 0;
  if ( T[u].left != NIL ) deg++;
  if ( T[u].right != NIL ) deg++;
  printf("degree = %d, ", deg);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);

  if ( T[u].parent == NIL )
    printf("root\n");
  else if ( T[u].left == NIL && T[u].right == NIL )
    printf("leaf\n");
  else
    printf("internal node\n");
}

int main() {
  int v, l, r, root = 0;
  scanf("%d", &n);

  for ( int i = 0; i < n; i++ ) T[i].parent = NIL;

  for ( int i = 0; i < n; i++ ) {
    scanf("%d %d %d", &v, &l, &r);
    T[v].left = l;
    T[v].right = r;
    if ( l != NIL ) T[l].parent = v;
    if ( r != NIL ) T[r].parent = v;
  }

  for ( int i = 0; i < n; i++ ) if ( T[i].parent == NIL ) root = i;

  setDepth(root, 0);
  setHeight(root);

  for ( int i = 0; i < n; i++ ) print(i);

  return 0;
}


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

class Plogram
{
    static void Main()
    {
        int num = int.Parse(Console.ReadLine());

        var list = new List<Money>();
        int rate;
        double total = 0;

        for(int i =0; i<num; i++)
        {
            var info = Console.ReadLine().Split();
            list.Add(new Money(double.Parse(info[0]), info[1]));
        }
        foreach (var n in list)
        {
            if (n.Type == "BTC")
            {
                rate = 380000;
            }
            else
            {
                rate = 1;
            }
            total += n.Amount * rate;
        }
        Console.WriteLine(total);
    }
}

class Money
{
    public double Amount { get; set; }
    public string Type { get; set; }

    public Money(double amount, string type)
    {
        Amount = amount;
        Type = type;
    }
}

Measured memory_bytes: 13140
object Main extends App {
    var get = readLine
    var n = get.split(" ")(0).toInt
    var m = get.split(" ")(1).toInt
    var c = get.split(" ")(2).toInt
    
  
    var get2 = readLine
	val b = new Array[Int](m)
    var get3 = readLine
    var a = new Array[Int](m)
  	var loop=0
  var sum=0
  var ans=0
  	while(loop<m) {
	  b(loop)=get2.split(" ")(loop).toInt
      loop+=1
    }
  	loop=0
  	var loop2=0
  	while(loop<n){
      while(loop2<m){
        sum+=b(loop2)*get3.split(" ")(loop2).toInt
      	loop2+=1
      }
      if(sum+c>0)
      	ans+=1
      sum=0
      loop2=0
      loop+=1
      get3 = readLine
    }      
  println(ans)
}

Measured memory_bytes: 27352
#include <bits/stdc++.h>
using namespace std;
struct top
{
    int a,b,c;

};

 int main() {
     int n,d,e,f;
     cin>>n;
      top s[n];
      for(int i=0;i<n;i++)
      {
          cin>>d>>e>>f;
          s[i].a=d;
          s[i].b=e;
          s[i].c=f;
      }
      for(int i=1;i<n;i++)
      {
          d=max(s[i-1].b,s[i-1].c);
          s[i].a=s[i].a+d;
          d=max(s[i-1].a,s[i-1].c);
          s[i].b=s[i].b+d;
          d=max(s[i-1].a,s[i-1].b);
          s[i].c=s[i].c+d;
      }
      d=(s[n-1].a>s[n-1].b)?((s[n-1].a>s[n-1].c)?s[n-1].a:s[n-1].c):((s[n-1].b>s[n-1].c)?s[n-1].b:s[n-1].c);
      cout<<d<<endl;
 }


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define SHOW(x) cout << #x << ": " << x << endl;
template<class T> ll sumArr(const T& a){ return accumulate(all(a), 0LL);}
template<class T> auto minArr(const T& a){ return *min_element(all(a));}
template<class T> auto maxArr(const T& a){ return *max_element(all(a));}
template<class T> void DEBUG_PRINT(T tmp){cout<<tmp<<endl;}
template<class T1,class... T2> void DEBUG_PRINT(T1 tmp,T2... tmp2){cout<<tmp<<" ";DEBUG_PRINT(tmp2...);}
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;


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

    ll n,ans = 0;
    cin>>n;
    unordered_map<ll,ll>mp;
    vector<int>a(n);
    rep(i,n){
        cin>>a[i];
        ans += mp[i - a[i]];
        mp[i + a[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 19228
#include <bits/stdc++.h>
using namespace std;
// C - Traveling Salesman around Lake

int main()
{
    int K, N;
    cin >> K >> N;
    int A[N] ;
    for (int i = 0; i < N ; i++)
    {
        cin >> A[i];
    }
    int m = 0;

    for (int i = 0; i < N - 1; i++)
    {
        if (i == 0)
        {
            int tmp = A[i] + K - A[N - 1];
            m = max(m, tmp);
        }
        else
        {
            m = max(m, A[i + 1] - A[i]);
        }
    }

    int mm = m;

    cout << K-mm << endl;
}

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

int main() {
  int N;
  int K;
  cin >> N >> K;
  
  int j = 1;
  
  for(int i = 0; i < N; i++) {
    int a = j * 2;
    int b = j + K;
    if(a > b) {
      j += K;
    }
    else {
      j *= 2;
    }
  }
  
  cout << j << endl;
}


Measured memory_bytes: 3608
/*
	Author: zhaodeyin
	Time: 2018.4.7
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
const int MaxN = 1e5 + 4;
typedef long long LL;
int main(){
	int a,b,k;
	cin>>a>>b>>k;
	if(k > (b-a+1)/2) {
		for(int i = a; i <= b; i++) cout<<i<<endl;
	}
	else {
		for(int i = a; i <= a+k-1; i++) cout<<i<<endl;
		for(int i = b-k+1; i <= b; i++) cout<<i<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int i, n, arr[100];
	const char *fmt = "%d";

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", arr+i);
	}
	for (i = n-1; i >= 0; i--) {
		printf(fmt, arr[i]);
		fmt = " %d";
	}
	putchar('\n');
	return 0;
}

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

#define endl '\n'

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

    int n, k; cin >> n >> k;
    int a[n];
    for (int i=0; i<n; i++) cin >> a[i];

    long double cur=0, ans=0;
    for (int i=0; i<k; i++){
        cur+= (a[i]+1)/2.0;
    }
    ans = cur;
    for (int i=1; i<n-k+1; i++){
        cur -= (a[i-1]+1)/2.0;
        cur += (a[i+k-1]+1)/2.0;
        if (ans < cur){
            ans = cur;
        }
    }
    cout << fixed << setprecision(9) << ans << endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int N,a[100010],b[100010],m=0,n=0;
int f[100010][2],num;
struct node{
	int x,y;
}p[100010];int cnt=0;
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]<=0) b[++m]=a[i];
		else a[++n]=a[i];
	}
	if(n==0)
	{
		for(int i=1;i<=m;i++) if(b[1]<b[i]) swap(b[1],b[i]);
		num=b[1];
		for(int i=2;i<=m;i++) p[++cnt].x=num,p[cnt].y=b[i],num-=b[i];
	}
	else
	{
		if(m==0)
		{
			for(int i=1;i<=n;i++) if(a[1]>a[i]) swap(a[1],a[i]);
			num=a[1];
			for(int i=2;i<n;i++) p[++cnt].x=num,p[cnt].y=a[i],num-=a[i];
			p[++cnt].x=a[n];p[cnt].y=num;
			num=a[n]-num;
		}
		else
		{
			a[++n]=a[1];a[1]=b[m];m--;
			num=a[1];
			for(int i=2;i<n;i++) p[++cnt].x=num,p[cnt].y=a[i],num-=a[i];
			p[++cnt].x=a[n];p[cnt].y=num;
			num=a[n]-num;
			for(int i=1;i<=m;i++) p[++cnt].x=num,p[cnt].y=b[i],num-=b[i];
		}
	}
	printf("%d\n",num);
	for(int i=1;i<=cnt;i++) printf("%d %d\n",p[i].x,p[i].y);
}

Measured memory_bytes: 3456
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)
 
func run() {

	A := nextInt();
    B := nextInt();
    T := nextInt();
	solve(A, B, T);

}

func solve(A int64, B int64, T int64){
	Println((T/A)*B)
}


// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int64 {
	a, err := strconv.ParseInt(next(),10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}
 
func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}


Measured memory_bytes: 2816
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    const int sum_a = accumulate(a.begin(), a.end(), 0LL);

    cout << (n - sum_a >= 0 ? n - sum_a : -1) << endl;
}


Measured memory_bytes: 3692
#include <cstdio>
#include <algorithm>


using namespace std;

int N,X,Y;

const int MAXN=2e3+5;

int dist_cnt[MAXN];

int main(){
    
    scanf("%d%d%d",&N,&X,&Y);

    for(int i=1;i<=N;i++)
        for(int j=i+1;j<=N;j++){
            int dist=abs(j-i);
            dist=min(dist,abs(i-X)+abs(j-Y)+1);
            dist=min(dist,abs(i-Y)+(j-X)+1);

            dist_cnt[dist]++;
        }
    
    for(int d=1;d<=N-1;d++)
        printf("%d\n",dist_cnt[d]);

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int n, m;
vector<pii> v;

signed main() {

    cin >> n >> m;
    int a, b;

    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        v.bash({b,a});
    }

    sort(ALL(v));

    int ans = 0;
    int p = 0;

    for(int i = 0; i < m; i++) {
        if(!ans || v[i].second > p) {
            p = v[i].first -1;
            ans++;
        }
    }

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



Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    REP(i,5) {
        int x;
        cin >> x;
        if(!x) {
            cout << i+1 << endl;
            return;
        }
    }
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define P pair<int,int>
#define PI 3.141592653589793
const int INF = 1001001001;

int main() {
	int n,m;
	cin >> n >> m;
	vector<ll> h(n);
	rep(i, n) cin >> h[i];

	vector<int> check(n, 1);
	rep(i, m) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		if (h[x] > h[y]) swap(x, y);
		if (h[x] < h[y]) {
			check[x] = 0;
		}
		else{
			check[x] = 0;
			check[y] = 0;
		}
	}
	int ans = 0;
	rep(i, n) {
		ans += check[i];
	}
	cout << ans << endl;
}


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

using namespace std;

main(){
    int A,B,C,D;
    scanf("%d %d %d %d",&A,&B,&C,&D);
    if(C>B or A>D) cout << 0;
    else if(A<C){
        if(D<B) cout << abs(C-D);
        else cout << abs(C-B);
    }else{
        if(B<D) cout << abs(A-B);
        else cout << abs(A-D);
    }
}

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

using namespace std;

int main(){
    string S; cin >> S;
    bool flag = true;
    for (int i = 0; i < S.length() - 1; i++){
        if (S[i] == S[i + 1]){
            flag = false;
        }
    }

    if (flag == true){
        cout << "Good" << endl;
    }else{
        cout << "Bad" << endl;
    }
    
    

    return 0;
}

Measured memory_bytes: 256
def selection_sort(nums, n):
    c = 0

    for i in range(n):
        minj = i

        for j in range(i, n):
            if nums[j] < nums[minj]:
                minj = j

        if i != minj:
            nums[i], nums[minj] = nums[minj], nums[i]
            c += 1

    return (c, nums)

def main():
    n = int(input())
    nums = [int(x) for x in input().split()]

    c, nums = selection_sort(nums, n)

    print(" ".join([str(x) for x in nums]))
    print(c)

if __name__ == '__main__':
    main()



Measured memory_bytes: 5608
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <limits>
#include <math.h>
#include <iomanip>
#define int long long
//#define int double
//#define int unsigned long long
#define ll long long
#define double long double
using namespace std;
//#pragma endregion

signed main()
{
	// 10^18 = 1000000000000000000

	//int h1, h2, m1, m2, k;
	//int box, box1,box2;

	//int N;
	int n;
	//char n;
	//int a, b, c;
	//int m;
	int h, w, x;
	int k;
	//int d,t,s;
	//int t;
	//string s;
	//string t;
	//int m1, m2;
	//int a, b, c, k;
	//int x, y;

	string s;
	string t;
	//string s[100000];
	//string c[7];
	//int a[100000];
	//int b[200000];
	//int a[2000000] = { 0 };
	//int b[2000000] = { 0 };
	//int a[20000] = { 0 };
	//int b[20000] = { 0 };
	//vector<int>a(2000000);
	//vector<int>b(2000000);

	//int aaa = 0;
	//int bbb = 0;

	int box[20000] = { 0 };
	//char box[20000];
	//int a[2000000] = { 0 };
	//int box = 0;
	//int box[7][7] = { 0 };
	//int box2;
	//int p[1111];
	//int x[2000], y[2000];
	//int l[100];


	//long double aaa;

	int count = 0;
	//int k, d;
	//int a = 0;
	int all = 0;
	//double all;
	//double a, b;
	//double h, m;
	//int a[30000] = { 0 };
	//double c, d, e;

	//double mbox, hbox;
	//double box, box2;

	bool flag = true;
	//bool flag = false;

	//string str;

	//cin >> h1 >> m1 >> h2 >> m2 >> k;
	cin >> n;
	//cin >> a >> b >> c;
	//cin >> s;
	//cin >> t;
	//cin >> d >> t >> s;
	//cin >> n >> x >> t;

	/*for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}*/
	if (n == 0)
	{
		cout << "1\n";
	}
	else
	{
		cout << "0\n";
	}

	/*count = d / s;

	if (count <= t)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	/*do {
		for (int i = 0; i < n; i++) {
			if (i % n == 0)
				cout << "\n";
			cout << a[i] << " ";
		}
	} while (next_permutation(a, a + n));*/

	//getline(cin, s);

	/*for (int i = 0; i < count; i++)
	{
		all += s[i] - '0';
	}*/

	//n = s.length();

	//sort(box, box + count);
	//sort(p, p + n);
	//n = n - 'Z';

	//box = n % 26;

	//for (int i = 0; i < k; i++)
	//{
	//	all += p[i];
	//}

	//all = n + (n * n) + (n * n * n);

	/*if (n > 0)
	{
		cout << "a\n";
	}
	else
	{
		cout << "A\n";
	}*/
	//n = t.length();

	/*cout << "AC x " << ac << "\n";
	cout << "WA x " << wa << "\n";
	cout << "TLE x " << tle << "\n";
	cout << "RE x " << re << "\n";*/

	//cout << x << "\n";
	//cout << all << "\n";
	//cout << box << "\n";
	//cout << a << b << c << "\n";

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	//cout << fixed << setprecision(111) << all;
	//return 0;
}


Measured memory_bytes: 3624
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<math.h>
#define loop(i, l, r) for(i=l; i<r; i++)/*Instead of function, (for).*/
#define rep(i,r) for(i=0; i<r; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long int lli;
/*Return Combination ,(nCr)*/
int combi(int n, int r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
/*Return gcd(a, b)*/
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}
int main(void)
{
	int i, n;
	scanf("%d", &n);
	int a[n];
	rep(i,n){
	 	scanf("%d", &a[i]);
		if(a[i]%2 == 0){
			if(a[i]%3 ==0 || a[i]%5 == 0){
				;
			}else{
				puts("DENIED");
				return 0;
			}
		}
	}
	puts("APPROVED");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
constexpr ll mod = (ll)(1e9 + 7);

constexpr ll MAX = 300000;
ll frac[MAX + 1];
ll inv[MAX + 1];
ll invfrac[MAX + 1];

ll power(ll p, ll n)
{
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return (power(p, n - 1) * p) % mod;
    } else {
        const ll pp = power(p, n / 2);
        return (pp * pp) % mod;
    }
}

ll comb(ll n, ll k)
{
    if (k < 0) {
        return 0;
    }
    if (k == 0 or k == n) {
        return 1;
    }
    return (((frac[n] * invfrac[k]) % mod) * invfrac[n - k]) % mod;
}

int main()
{
    frac[1] = 1;
    inv[1] = 1;
    invfrac[1] = 1;

    for (ll i = 2; i <= MAX; i++) {
        frac[i] = (frac[i - 1] * i) % mod;
        inv[i] = power(i, mod - 2);
    }
    for (ll i = 2; i <= MAX; i++) {
        invfrac[i] = (invfrac[i - 1] * inv[i]) % mod;
    }

    ll N, M, K;
    cin >> N >> M >> K;

    ll sum = 0;
    for (ll k = 0; k <= K; k++) {
        const ll vert = (comb(N + 2 * k, k) - comb(N + 2 * k, k - 1) + mod) % mod;
        const ll hori = (comb(M + 2 * (K - k), (K - k)) - comb(M + 2 * (K - k), (K - k) - 1) + mod) % mod;
        const ll combination = (((vert * hori) % mod) * comb(N + M + 2 * K, N + 2 * k)) % mod;
        sum = (sum + combination) % mod;
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 10128
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100,mo=1e9+7;
int n,m,i,j,k,x,a[N],f[51][N][N],ans;
void add(int &x,int k){x=(x+k)%mo;}
int main(){
	scanf("%d",&n);m=2*n-1;
	for (i=1;i<=m;i++) scanf("%d",&a[i]);
	sort(a+1,a+m+1);f[1][1][1]=1;
	for (i=1;i<n;i++){
		int l=a[n-i]!=a[n-i+1],r=a[n+i]!=a[n+i-1];
		for (j=1;j<=m;j++) for (k=1;k<=m;k++) if (f[i][j][k]){
			int tj=j+l+r,tk=k+l,v=f[i][j][k];
			for (x=1;x<tk;x++) add(f[i+1][tj-(tk-x-1)][x],v);
			add(f[i+1][tj][tk],v);
			for (x=tk+1;x<=tj;x++) add(f[i+1][tj-(x-tk-1)][tk+1],v);
		}
	}
	for (i=1;i<=m;i++) for (j=1;j<=m;j++) add(ans,f[n][i][j]);
	printf("%d",ans);
}

Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n, a, b, totA = 0, totB = 0;
        String[] elems;
        while((n = Integer.parseInt(sc.nextLine())) > 0) {
            for (int i = 0; i < n; i++) {
                elems = sc.nextLine().split(" ");
                a = Integer.parseInt(elems[0]);
                b = Integer.parseInt(elems[1]);

                if(a > b) {
                    totA += a + b;
                } else if(a < b) {
                    totB += a + b;
                } else {
                    totA += a;
                    totB += b;
                }
            }
            System.out.println(totA + " " + totB);
            totA = 0;
            totB = 0;
        }
    }
}

Measured memory_bytes: 66828
# -*- coding: utf-8 -*-
import sys
import math
#import collections
#sys.setrecursionlimit(100000)

tmp = input().split()
n,m = list(map(lambda a: int(a), tmp))

a=[]
for i in range(n):
	a.append(-1)

for i in range(m):
	tmp = input().split()
	s,c = list(map(lambda a: int(a), tmp))
	if(a[s-1]!=c)and(a[s-1]!=-1):
		print(-1)
		sys.exit()
	a[s-1]=c

if(a[0]==0)and(n==1):
	print(0)
	sys.exit()
if(a[0]==-1)and(n==1):
	print(0)
	sys.exit()


if(a[0]==0):
		print(-1)
		sys.exit()

for i in range(n):
	if(a[i]==-1):
		if(i==0):
			a[i]=1
		else:
			a[i]=0

ans=0
for i in range(n):
	ans*=10
	ans+=a[i]
print(ans)








Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int           long long
#define pb            push_back
#define ppb           pop_back
#define si            set <int>
#define endl          '\n'
#define fr            first
#define sc            second     
#define rep(i,a,b)    for(int  i=a;i<b;i++)
#define repr(i,a,b)      for(int i=b-1;i>=a;i--)
#define trav(it,v)      for(auto it=v.begin();it!=v.end();it++)
#define all(v)        v.begin(),v.end()
#define srt(v)        sort(all(v))
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define bs            binary_search
#define sp(n)         setprecision(n)
#define spl           " "
#define arr(a,n)      rep(i,0,n) cin>>a[i]
#define mod           998244353
#define MAXN             10001

using namespace std;

bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
       return (a.first > b.first); 
} 


//int dx[4]={0,0,1,-1};
//int dy[4]={1,-1,0,0};
void solve()
{
    
    int n,m;
    cin>>n>>m;
    int a[n],tot=0;
    rep(i,0,n)
    {
        cin>>a[i];
        tot+=a[i];
    }
    sort(a,a+n);
    int p=4*m;
    int mn=tot/p;
    if(tot%p!=0)
        mn++;
    int ans=0;
    repr(i,0,n)
    {
        if(a[i]>=mn)
            ans++;
    }
    if(ans>=m)
        cout<<"Yes";
    else
        cout<<"No";

    
    
}	
	


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
    //cin>>t;
    while(t--)
    {
    	solve();
    }
}

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

int N;
int a[400];
int csum[401];
int dp[400][400];

int solve(int l, int r) {
 if(l==r) return 0;
 if(dp[l][r] != 0) return dp[l][r]; 

 int ret = 1LL<<60;
 for(int m = l; m<r; m++) ret = min(ret, solve(l,m) + solve(m+1,r));
 return dp[l][r] = ret + (csum[r+1] - csum[l]);
}

signed main() {
  cin >> N;
  for(int i=0; i<N; i++) cin >> a[i];
  csum[0] = 0;
  for(int i=1; i<=N; i++) csum[i] = csum[i-1] + a[i-1];

  cout << solve(0,N-1) << endl;
}


Measured memory_bytes: 1536
import sys
n,y = map(int,input().split())

for i in range(n+1):
    for j in range(n+1-i):
        k = n - i - j
        if i*10000 + j*5000 + k*1000 == y:
            print(i,j,k)
            sys.exit()
print(-1,-1,-1)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int ans = 0;
    int hole = 1;
    if (B == 1) {
      System.out.println(0);
      return;
    }
    hole = A;
    ans = 1;
    while (hole < B) {
      hole += A - 1;
      ans++;
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 22612
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
// #define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int dpp[5005][5005];
int dps[5005][5005];
int ans=0;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dpp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        {
            if(j-a[i]>=0)
                dpp[i][j]|=dpp[i-1][j-a[i]];
            dpp[i][j]|=dpp[i-1][j];
        }
    }

    dps[n+1][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=k;j++)
        {
            if(j-a[i]>=0)
                dps[i][j]|=dps[i+1][j-a[i]];
            dps[i][j]|=dps[i+1][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        int z=a[i];
        int x=k,y=0;
        int tt=k-a[i];
        int mn=1e9;

        while (x>=0&&y<=k)
        {
            while (x>=0&&dpp[i-1][x]==0)
            {
                x--;
            }
            while (y<tt-x && y<=k)
            {
                y++;
            }
            while (dps[i+1][y]==0 && y<=k)
            {
                y++;
            }
            if(x>=0)
            if(x+y>=tt &&(dpp[i-1][x]&dps[i+1][y]))
            {
                mn=min(mn,x+y);
            }            
            x--;
        }        
        if(mn<k)
            ans++;
    }

    cout<<n-ans;
} 



Measured memory_bytes: 195840
import numpy as np
A1 = list(map(int, input().strip().split()))
A2 = list(map(int, input().strip().split()))
A3 = list(map(int, input().strip().split()))
N = int(input())
b = [int(input()) for i in range(N)]
A = np.array([A1, A2, A3])
K = np.empty((3, 3))

for i in range(3):
    for j in range(3):
        if A[i][j] in b:
            K[i][j] = 1
        else:
            K[i][j] = 0

if (3 in K.sum(axis=1)) or (3 in K.sum(axis=0)) or (K[0][0] == 1 and K[1][1] == 1 and K[2][2]) or (K[0][2] == 1 and K[1][1] == 1 and K[2][0]):
    print("Yes")

else:
    print("No")

Measured memory_bytes: 12504
#include<iostream>
#include <algorithm>
#define int long long
#define roop(i,n) for(int i=0;i<n;i++)
using namespace std;
int f[12] = {1,6,36,216,1296,7776,46656,9,81,729,6561,59049};
int dp[114514];
signed main() {
	int n;
	cin >> n;
	dp[0] = 0;
	roop(i, n)dp[i + 1] = 1145141919;
	roop(i, n) {
		roop(j, 13) {
			if (i+1 >= f[j]) {
				dp[i+1] = min(dp[i+1],dp[i+1-f[j]]+1);
			}
		}
	}
	cout << dp[n] << endl;
}

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

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n)  FOR(i,0,(n))
typedef vector<int> vec;


class CSpecialTrains {
public:
	void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    vec c(n - 1), s(n - 1), f(n - 1);
    REP(i, n-1) in >> c[i] >> s[i] >> f[i];
    REP(i, n ) {
      int t = 0;
      FOR(j,i,n - 1){
        if(t < s[j]) t = s[j];
        else if(t % f[j] == 0) t += 0;
        else t = t + f[j] - (t % f[j]);
        t += c[j];
      }
      out << t << endl;
    }
	}
};


signed main() {
  ios::sync_with_stdio(false);
  cout.tie(0);
  cout << fixed;
	CSpecialTrains solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3620
N =int(input())
def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)

A = digitSum(N)
if A%9 == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 11096
import sys
N,M=map(int,input().split())
A=list(set(map(int,input().split())))
N=len(A)
A=[a//2 for a in A]
 
def f(x):
    cnt=0
    while x%2==0:
        x//=2
        cnt+=1
    return cnt
C=f(A[0])
for a in A:
    if f(a)!=C:
        print(0)
        sys.exit()
def lcm(x,y):
    xy=x*y
    while y!=0:
        x,y=y,x%y
    return xy//x
LCM=A[0]
for i in range(1,N):
    LCM=lcm(LCM,A[i])
if LCM>M:
    ans=0
else:
    M//=LCM
    ans=(M+1)//2
print(ans)

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

int main(){
  int x1, y1, x2, y2;

  cin >> x1 >> y1 >> x2 >> y2;


  int mx, my;
  mx = x2 - x1;
  my = y2 - y1;

  int x3, y3, x4, y4;

  x3 = x2-my;
  y3 = y2+mx;

  mx = x3 - x2;
  my = y3 - y2;

  x4 = x3-my;
  y4 = y3+mx;


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

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  
using namespace std;  
#define INF 0x3f3f3f3f  
typedef long long ll;  
const int N =  100010;  
#define FI first
#define SE second
typedef pair<int, int>pii;
int num[N];
bool vis[N];
int main()  
{  
 //  freopen("in.txt","r",stdin);
   int n;
   while (cin >> n)
   {
   	 memset(vis, 0, sizeof(vis));
   	 for (int i = 1; i <= n; i++)
   	 	cin >> num[i];
   	 int cur = 1, ans = 0;
   	 while (cur != 2 && !vis[cur])
   	 {
   	 	ans++;
   	 	vis[cur] = 1;
   	 	cur = num[cur];
   	 }
   	 if (cur == 2)
   	 	printf("%d\n", ans);
   	 else
   	 	puts("-1");

   }
   return 0;  
}  

Measured memory_bytes: 896
N, M = map(int,input().split())
state = []
for _ in range(M):
  lst = list(map(int, input().split()))
  state.append(lst[1:])#switch numbers each denkyu
p = list(map(int, input().split()))#numbers switches on %2 == pi 
ans = 0
for i in range(2**N):
  total = 0
  for j in range(M):
    cnt = 0
    for s in state[j]:
      s -= 1
      if (i >> s) & 1:#全スイッチのパターン一つ一つについて、各電球の各スイッチがオンになっているか
        cnt += 1
    cnt %= 2
    if cnt == p[j]:
      total += 1
    else:
      break
  if total == M:
    ans += 1
print(ans)

Measured memory_bytes: 9060
#include<bits/stdc++.h>
#define U [1<<17]={}
#define G(a)((c=A[a]+A[P[a]]+C[a])%k?c:0)
typedef long long L;using namespace std;map<L,L>T U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c,p;char s U;
L D(L a){L d;Z[a]=1;for(map<L,L>::iterator I=T[a].begin();I!=T[a].end();I++)
    d=I->first,d-P[a]?P[d]=a,E[d]=E[a]+1,C[d]=I->second,D(d),Z[a]+=Z[d],!H[a]|Z[H[a]]<Z[d]?H[a]=d:0:0;}
L M(L i){return i?B[i]+M(i^i&-i):0;}
L S(L x,L i){for(x=G(x)+M(i++)-M(i);i<1e5;i+=i&-i)B[i]+=x;}
L K(L a){p=X[a];n=X[b];return p-n?E[p]<E[n]?swap(p,n),swap(a,b),0:0,M(O[a])-M(O[p])+G(p)+K(P[p]):abs(M(O[a])-M(O[b]));}
main(){for(cin>>n>>k;++p<n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;
       for(D(b=p=0);p<n;p++)if(!p|H[P[p]]-p)for(a=p;!b|a;S(a=H[a],O[a]=b++))X[a]=p;
       for(cin>>a;cin>>s>>a>>b;*s&2?cout<<K(a)<<endl,0:A[a]+=b,S(H[a],O[a]),a&&S(a,O[a]-1));}

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

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

#define MP make_pair
#define MT make_tuple
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()

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

	int N;
	cin >> N;
	string s, t;
	cin >> s >> t;

	int ret = N;
	REP(i, N){
		bool ok = true;
		FOR(x, i, N){
			if(s[x] != t[x - i]){
				ok = false;
				break;
			}
		}
		if(ok){
			ret = i;
			break;
		}
	}

	cout << N + ret << endl;

	return 0;
}


Measured memory_bytes: 256