akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define EPS 0
typedef struct{
	double x,y;
}point;

point make(double x,double y){
	point res;
	res.x=x;
	res.y=y;
	return res;
}
//a-b
point vec(point a,point b){
	point res;
	res.x=a.x-b.x;
	res.y=a.y-b.y;
	return res;
}

// a・b
double dot(point a,point b){
	return a.x*b.x+a.y*b.y;
}
//|a|
double  norm(point a){
return sqrt(dot(a,a));
}
//|a|^2
double absolute(point a){
return dot(a,a);
}
//a×ｂ　外積z成分
double cross(point a,point b){
return a.x*b.y-a.y*b.x;
}
//a=x1+iy1,b=x2+iy2 a*b
point imaseki(point a,point b){
point res;
res.x=a.x*b.x-a.y*b.y;
res.y=a.x*b.y+a.y*b.x;
return res;
}
//共役
point conjugate(point a){
point res;
res.x=a.x;
res.y=-a.y;
return res;
}


int ccw(point p0,point p1,point p2){
point a=vec(p1,p0);
point b=vec(p2,p0);
	if(cross(a,b)>EPS){
	return 1;//counter_clockwise
	}else if(cross(a,b)<EPS){
	return -1;//clockwise
	}else if(dot(a,b)<-EPS){
	return 2;//online_back
	}else if(absolute(a)<absolute(b)){
	return -2;//online_front
	}else{
	return 0;//on_segment
	}

}
//交差判定　s1-s2 s3-s4
bool intersect(point s1,point s2,point s3,point s4){
 if(ccw(s1,s2,s3)*ccw(s1,s2,s4)<=0 && ccw(s3,s4,s1)*ccw(s3,s4,s2)<=0)
        return true;
    return false;
}

int main(){
int q;
cin>>q;
for(int i=0;i<q;i++){
point s1,s2,s3,s4;
double x,y;
cin>>x>>y;
s1=make(x,y);
cin>>x>>y;
s2=make(x,y);
cin>>x>>y;
s3=make(x,y);
cin>>x>>y;
s4=make(x,y);
if(intersect(s1,s2,s3,s4)){
cout<<1<<endl;
}else{
cout<<0<<endl;
}

}
return 0;
}



Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
	x=0;
	static int p;p=1;
	static char c;c=getchar();
	while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
	while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
	x*=p;
}
int n;
int main()
{
//	freopen("mnth.in","r",stdin);
//	freopen("mnth.out","w",stdout);
	read(n);
	int ans=0x7f7f7f7f;
	for(int i=1;i<n;i++)
	{
		int sum=0;
		int x=i;
		while(x)
		{
			sum+=x%10;
			x/=10;
		}
		x=n-i;
		while(x)
		{
			sum+=x%10;
			x/=10;
		}
		ans=min(ans,sum);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define ll long long

void solve()
{
    ll N;
    cin >> N;

    cout << N * N * N << endl;
}

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


Measured memory_bytes: 256
n = gets.strip.to_i

n.times.each do
  s, e = gets.strip.split(' ').map{|s| s.to_i}

  min_rt = nil

  for direc in [-1, 1]
    next if s > 5 && direc < 0

    nxt = s
    rt = [nxt]
    while nxt != e
      nxt += direc
      if nxt < 0
        nxt = 1
        direc = 1
      elsif nxt > 9
        nxt = 5
        direc = -1
      end
      rt << nxt
    end

    if min_rt.nil? || min_rt.length > rt.length
      min_rt = rt
    end
  end

  puts min_rt.join(' ')
end

Measured memory_bytes: 6116
import java.lang.Math.min

fun main(args: Array<String>) {
    val (d, g) = readIntList()
    val p = List(d) { readIntList() }

    var ans = Int.MAX_VALUE
    for (mask in 0 until (1 shl d)) {
        var s = 0
        var num = 0
        var restMax = -1
        for (i in 0 until d) {
            if ((mask shr i) and 1 == 1) {
                s += 100 * (i + 1) * p[i][0] + p[i][1]
                num += p[i][0]
            } else {
                restMax = i
            }
        }
        if (s < g) {
            var s1 = 100 * (restMax + 1)
            var need = (g - s + s1 - 1) / s1
            if (need >= p[restMax][0]) continue
            num += need
        }
        ans = min(ans, num)
    }
    println(ans)
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 36468
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


ll gcd(ll a,ll b){
    if(b == 0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}

ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

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

    ll ans = 0;
    for(ll i=0;i<1000;++i){
        ll c[3];
        c[0] = i / 100;
        c[1] = (i / 10) % 10;
        c[2] = i % 10;
        ll index = 0;
        for(ll j=0;j<n;++j){
            if(s[j] == (c[index] + '0')){
                index++;
            }
            if(index == 3){
                break;
            }
        }
        if(index == 3){
            ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>

#define ull unsigned long long
#define ul unsigned long
#define ll long long
#define size_t long long
// std::sort(&a[0], &a[4], [](auto& x, auto& y){return x[0] < y[0];});
//accumulate(&arr2[n], &arr2[m-1], 0);
using namespace std;

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

  int N;
  std::cin >> N;
  ll A[N] = {};
  ll k1 = 0;
  ll temp = 1;
  for (size_t i = 0; i < N; i++) {
    std::cin >> A[i];
    k1 = k1 + A[i]*temp;
    temp *= -1;
  }
  A[0] -= k1/2;
  std::cout << k1 << " ";
  for (size_t i = 0; i < N - 1; i++) {
    std::cout << A[i]*2 << " ";
    A[i+1] = A[i+1] - A[i];
  }

  std::cout << "" << '\n';

  return 0;
}


Measured memory_bytes: 2176
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>


using namespace std;
const int MOD = 1000000009; // check!!!
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)


int main(){
	double a,b; cin>>a>>b;
	printf("%.15f\n",a*b/3.305785);

	return 0;
}

Measured memory_bytes: 1236
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",max(a*b,c*d));
}

Measured memory_bytes: 128
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 t = 0;

		while ((a - 1) * t + 1 < b) {
			t++;
		}
		System.out.println(t);
		sc.close();
	}
}


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

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
vector<T> Vec(int n, T v)
{
    return vector<T>(n, v);
}
template <class... Args>
auto Vec(int n, Args... args)
{
    auto val = Vec(args...);
    return vector<decltype(val)>(n, move(val));
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    map<ll, int> num;
    for (int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        num[a]++;
    }
    ll ans = 0;
    for (const auto& p : num) {
        if (p.second >= p.first) {
            ans += p.second - p.first;
        } else {
            ans += p.second;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6272
s=input()
if len(s)==2:
    if len(set(s))==1:
        print(1,2)
        exit()
    else:
        print(-1,-1)
        exit()
        
for i in range(len(s)-2):
    a=s[i:i+3]
    if len(set(a))<=2 :
        print(i+1,i+3)
        exit()
print(-1,-1)

Measured memory_bytes: 3188
k=int(input())
l=list(range(1, k+1))
import itertools
import math
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd, numbers)
ans=0
for v in itertools.combinations_with_replacement(l, 3):
  if v[0]==v[1]==v[2]:
    ans+=gcd(*v)
  elif v[0]==v[1]:
    ans+=gcd(*v)*3
  elif v[1]==v[2]:
    ans+=gcd(*v)*3
  elif v[0]==v[2]:
    ans+=gcd(*v)*3
  else:
    ans+=gcd(*v)*6
print(ans)

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

int main() {
  int i,N,K,Q,x;
  cin >> N >> K >> Q;
  vector<int> A(N,K);
  for(i=0; i<Q; i++) {
    cin >> x;
    A.at(x-1)++;
  }
  for(i=0; i<N; i++) {
    if(A.at(i)-Q > 0)
      cout << "Yes";
    else
      cout << "No";
    cout << endl;
  }
}

Measured memory_bytes: 1024
//codeforces
#include <algorithm>
#include <vector>
#include <string>
#include <ctype.h>
#include <set>
#include <map>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<time.h>
#include<string>
#include<stack>
#include<cmath>
#include<iostream>
#include<cstring>
#include<complex>
#include<bitset>
#include <climits>
#include<tr1/unordered_set>
#include<tr1/unordered_map>


#define FOR(i,j,k) for(int i=j;i<k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
//Make sure no overflow problems
//#define int long long
#define pii  pair<int, int>
#define vi vector<int >
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define VAR(i,n) __typeof(n) i = (n)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)
#define FORDEACH(i,c) for( VAR(i,(c).rbegin()),i!=(c).rend();i++)
#define REP(i,n) FOR(i,0,n)
#define ld long double
const int INF = 1e9+7;
const long long INFLL = (ll)INF * (ll)INF;
const ld EPS = 10e-9;

using namespace std;

class TrieNode{
    public:
    bool isword;
    char c;
    map<char,TrieNode*> m;
    string word;
    public:
    TrieNode(){}
    TrieNode(char ch){
        c=ch;
        isword=false;
    }
};

void insert(TrieNode* root,string word){
    TrieNode* temp=root;
    for(char c:word){
        if(temp->m.find(c)==temp->m.end())
            temp->m[c]=new TrieNode(c);
        temp=temp->m[c];
    }
    temp->isword=true;
    temp->word=word;
}

#pragma GCC optimize ("Ofast")
static auto _ = [] { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0); return 0; } ();

int main() {
    int n,W;
    cin>>n>>W;
    // vector<int> v(n),w(n);
    // for(int i=0;i<n;i++){
    //     cin>>w[i]>>v[i];
    // }

    // vector<vector<long long>> dp(n+1,vector<long long> (W+1,0));

    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=W;j++){
    //         if(w[i-1]<=j)
    //             dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i]);
    //         else
    //             dp[i][j]=dp[i-1][j];
    //     }
    // }
    // cout<<dp[n][W];

    vector<long long> dp(W+1);
    for(int i=0;i<n;i++){
        int val,wt;
        cin>>wt>>val;
        for(int j=W-wt;j>=0;j--){
            dp[j+wt]=max(dp[j+wt],dp[j]+val);
        }
    }
    cout<<*max_element(dp.begin(),dp.end());

    return 0;
}


Measured memory_bytes: 3892
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<climits>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007

int dat[100];
int N,M,Q;
int a[100],b[100],c[100],d[100];

int dfs(int n,int k){
    int ans=0;
    if(k==N+1){
        //cout<<dat[1]<<","<<dat[2]<<","<<dat[3]<<endl;
        for(int i=0;i<Q;i++){
            //cout<<i<<","<<dat[b[i]]<<","<<dat[a[i]]<<","<<c[i]<<endl;
            if(dat[b[i]]-dat[a[i]]==c[i]) ans+=d[i];
        }
        //cout<<ans<<endl;
        return ans;
    }
    for(int i=n;i<=M;i++){
        dat[k]=i;
        ans=max(ans,dfs(i,k+1));
    }
    return ans;
}
signed main(){
    cin>>N>>M>>Q;
    for(int i=0;i<Q;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }

    cout<<dfs(1,1)<<endl;
}


Measured memory_bytes: 3192
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;


int main() 
{
   int n;
   cin >> n;
   map<string,int>mp;
   for(int i=0; i<n; i++){
      string a;
      cin >> a;
      mp[a]++;
   }
   map<string,int>::iterator it;
   int m = 0;
   for(it=mp.begin(); it!=mp.end(); it++){
       m = max(m, it->second);
   }
   for(it = mp.begin(); it!=mp.end(); it++){
       if(it->second==m) cout << it->first << "\n";
   }
}

Measured memory_bytes: 25216
using System;

namespace id_0630cs
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            var b = int.Parse(Console.ReadLine());
            var c = int.Parse(Console.ReadLine());
            var d = int.Parse(Console.ReadLine());
            var e = int.Parse(Console.ReadLine());

            var totalSeconds = 0;
            if (a < 0)
            {
                totalSeconds = -a * c + d + b * e;
            }
            else
            {
                totalSeconds = (b - a) * e;
            }
            Console.WriteLine(totalSeconds);
        }
    }
}



Measured memory_bytes: 15940
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(defmacro println (obj &optional (stream '*standard-output*))
  `(let ((*read-default-float-format* 'double-float))
     (prog1 (princ ,obj ,stream) (terpri ,stream))))

(defconstant +mod+ 1000000007)

;; Hauptteil

(defun main ()
  (let* ((s (coerce (read-line) 'simple-base-string))
         (zeros 0)
         (ones 0))
    (loop for c across s
          do (if (char= c #\0)
                 (incf zeros)
                 (incf ones)))
    (println (* 2 (min zeros ones)))))

#-swank(main)


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

using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(vr) vr.begin(),vr.end()

typedef long long ll;
ll x,n;
ll r,s,p,k,ans,dem;
string t;

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   //freopen("input.txt","r",stdin);
   cin >> n >> k;
   cin >> r >> s >> p;
   cin >> t;
   t='@'+t;
   for(int i=1;i<=k;i++) t=t+'@';
   dem=1;
   for(int i=1;i<=min(n,k);i++)
    for(int j=1;j<=n && j*k+i<=n+k;j++){
        if (j*k+i>n+k) break;
        if (t[j*k+i]!=t[(j-1)*k+i]){
            if (dem!=0){
                dem+=(dem%2==1);
                if (t[(j-1)*k+i]=='r') ans+=p*(dem/2);
                if (t[(j-1)*k+i]=='s') ans+=r*(dem/2);
                if (t[(j-1)*k+i]=='p') ans+=s*(dem/2);
                dem=1;
                continue;
            }
            if (t[(j-1)*k+i]=='r') ans+=p;
            if (t[(j-1)*k+i]=='s') ans+=r;
            if (t[(j-1)*k+i]=='p') ans+=s;
        } else dem++;
    }
    cout << ans << endl;
   return 0;
}


Measured memory_bytes: 1168
n, q = gets.split.map(&:to_i)
s = gets.chomp
l, r = Array.new(q) { gets.split.map(&:to_i) }.transpose
cum = [0]
count = 0

n.times do |i|
  cum[i + 1] ||= count

  if s[i] == 'A' && s[i + 1] == 'C'
    count += 1
    cum[i + 2] = count
  end
end

l.zip(r).each { |l, r| puts cum[r] - cum[l] }

Measured memory_bytes: 15172
#include <iostream>

using namespace std;

int n;
int A[20];
int S[20];
int q;

bool solve(int i, int m) {
  if(i == n) {
    return m == 0;
  }

  if(solve(i + 1, m)) {
    return true;
  };

  if(solve(i + 1, m - A[i])) {
    return true;
  }

  return false;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }

  cin >> q;

  for (int i = 0; i < q; i++) {
    int m;
    cin >> m;
    if(solve(0, m)){
      cout << "yes" << endl;
    } else {
      cout << "no" << endl;
    }
  }
}



Measured memory_bytes: 3116
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#define ll long long
using namespace std;

int main(void){
    ll n;
    cin >> n;
    vector<ll> a;
    a.push_back(0);
    for(ll i = 0; i < n; i++){
        ll count;
        cin >> count;
        a.push_back(count);
    }
    a.push_back(0);
    ll ans = 0;
    for(ll i = 1; i < a.size(); i++)
        ans += abs(a[i]-a[i-1]);
    for(ll i = 1; i < a.size()-1; i++){
        if(a[i-1] < a[i] && a[i] > a[i+1])
            cout << ans - abs(a[i]-a[i-1]) - abs(a[i]-a[i+1]) + abs(a[i+1]-a[i-1]) << endl;
        else if(a[i-1] > a[i] && a[i] < a[i+1])
            cout << ans -abs(a[i]-a[i-1]) - abs(a[i]-a[i+1])+ abs(a[i+1]-a[i-1]) << endl;
        else
            cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 2164
from itertools import product

n, m = map(lambda x: int(x), input().split(' '))
k = []

for i in range(m):
    k.append(list(input().split(' ')[1:]))

p = list(map(lambda x: int(x), input().split(' ')))


on = list(product([False, True], repeat=n))
count = 0

for _on in on:
    for i, _k in enumerate(k):
        if not (([_on[int(__k) - 1] for __k in _k]).count(True) % 2) == p[i]:
            break
    else:
        count += 1

print(count)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
vector< int > v[150];
int main()
{
	int n , m;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++){
		int a , b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i = 1 ; i <= n ; i++){
		cout << v[i].size() << endl;
	}	
	return 0;
} 




Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    sa = [0]
    for a in A:
        sa.append(sa[-1]+a)

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1
        
    ans = 1
    p = 1
    for i in range(1, N+1):
        m = min(p*2, sa[-1] - sa[i])
        ans += m
        if m - A[i] < 0:
            return -1
        p = m - A[i]
    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()


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

int main() {
    //input
    int a,b;
    cin >> a >> b;
    if(a%3 == 0 || b%3 == 0 ||  (a+b)%3 == 0 ){
        cout << "Possible" << endl;
    }else{
        cout << "Impossible" << endl;
    }

    return 0;
}

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

using namespace std;
int main(void){

    int l,r;
    string in;
    stack<int> s;

    while(cin >> in){
        if(in=="+" or in=="-" or in=="*"){
            r = s.top();
            s.pop();
            l = s.top();
            s.pop();
            if(in=="+") s.push(l+r);
            if(in=="-") s.push(l-r);
            if(in=="*") s.push(l*r);
        }else{
            s.push(std::stoi(in));
        }
    }
    
    cout << s.top() << endl;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
    vector<ll> p(A), q(B), r(C), rm(C+1, 0), s, sm(X+Y+1, 0);
    rep(i,A) cin >> p[i];
    rep(i,B) cin >> q[i];
    rep(i,C) cin >> r[i];
    sort(ALL(p), greater<ll>());
    sort(ALL(q), greater<ll>());
    sort(ALL(r), greater<ll>());
    rep(i,X) s.push_back(p[i]);
    rep(i,Y) s.push_back(q[i]);
    sort(ALL(s), greater<ll>());
    rep(i,X+Y) sm[i+1] = sm[i] + s[i];
    reverse(ALL(sm));
    rep(i,C) rm[i+1] = rm[i] + r[i];
    ll ans = 0;
    rep(i,min(X+Y+1, C+1)) chmax(ans, sm[i] + rm[i]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7028
import Control.Monad
import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector as V

main = abc132b

abc132b = do
    [n] <- getIntList
    pL  <- getIntList
    let pV = V.fromList pL
    print $ count pV 0
    
count :: V.Vector Integer -> Integer -> Integer
count vec cnt
    | V.length vec < 3 = cnt
    | otherwise = let partial = V.take 3 vec
                   in if (partial V.! 0 < partial V.! 1 && partial V.! 1 < partial V.! 2) ||
                         (partial V.! 0 > partial V.! 1 && partial V.! 1 > partial V.! 2)
                         then count (V.tail vec) (cnt + 1)
                         else count (V.tail vec) cnt

readInt = fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words
getIntList = readIntList <$> BS.getLine

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

int gcdSolve(int a,int b){
  int x=min(a,b),y=max(a,b);
  bool c=true;
  while (x!=0&&y!=0){
    if(c)y%=x;
    else x%=y;
    c=!c;
  }
  return x+y;
};

int main(){
  int a,b;
  cin>>a>>b;
  cout<<gcdSolve(a,b)<<endl;
}



Measured memory_bytes: 3088
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		if(k%2==0) {
			System.out.println((k/2)*(k/2));
		}else {
			System.out.println((k/2+1)*(k/2));
		}
		sc.close();
	}
}


Measured memory_bytes: 23252
#include <stdio.h>
int main(){
	char a,b,c,d,e,f;
	scanf("%c%c%c%c%c%c", &a,&b,&c,&d,&e,&f);
	if(c==d && e==f) printf("Yes");
	else printf("No");  	

return 0 ;
}

Measured memory_bytes: 1628
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int k = input.nextInt();
        String s = input.next();
        if (k < s.length()){
            s = s.substring(0,k) + "...";
            System.out.println(s);
        } else {
            System.out.println(s);
        }
    }
}

Measured memory_bytes: 38472
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    int n,k; cin >> n >> k;
    vector<vector<int>> sushi(n);
    rep(i,n){
        int t,d; cin >> t >> d;
        t--;
        sushi[t].push_back(d);
    }

    vector<int> y0,y1;
    rep(i,n){
        if(sushi[i].size() == 0) continue;
        sort(ALL(sushi[i]));
        y1.push_back(sushi[i].back());  
        sushi[i].pop_back();
        y0.insert(y0.end(), ALL(sushi[i]));
    }
    sort(RALL(y0)); sort(RALL(y1));

    ll ans = 0;
    int Y = max(0, k-int(y0.size()));
    ll X = 0;
    rep(i,Y) X += y1[i];
    rep(i,k-Y) X += y0[i];
    while(true){        
        ans = max(ans, X + (ll)Y*Y);
        if(Y >= k || Y >= y1.size()) break;
        X += y1[Y];
        X -= y0[k-Y-1];
        Y++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=2e5+5;
const int mod=1e9+7;
//n<=2e5
//a[i],b[i]<=2e3
int fac[maxm],inv[maxm];
int a[maxm],b[maxm];
int d[4444][4444];
const int base=2e3+5;
int n;
int ppow(int a,int b,int mod){
    int ans=1%mod;a%=mod;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(){
    fac[0]=1;
    for(int i=1;i<maxm;i++)fac[i]=fac[i-1]*i%mod;
    inv[maxm-1]=ppow(fac[maxm-1],mod-2,mod);
    for(int i=maxm-2;i>=0;i--)inv[i]=(i+1)*inv[i+1]%mod;
}
int C(int n,int m){
    if(m<0||m>n)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++){
        d[-a[i]+base][-b[i]+base]++;
    }
    for(int i=1;i<=4010;i++){
        for(int j=1;j<=4010;j++){
            d[i][j]+=d[i-1][j]+d[i][j-1];
            d[i][j]%=mod;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=d[a[i]+base][b[i]+base];
        ans%=mod;
    }
    for(int i=1;i<=n;i++){
        ans-=C(2*(a[i]+b[i]),2*a[i]);
        ans%=mod;
    }
    ans=(ans*ppow(2,mod-2,mod)%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}
/*
发现a[i]和b[i]很小,是可以O(n^2)的范围

C(x+y,x)可以看作是(0,0)到(x,y)的方案数,
如果我们要求(0,0)到(x,y)的方案数,
可以令d[i][j]表示(0,0)到(i,j)的方案数,一开始d[0][0]=1.
转移方程为d[i][j]=d[i-1][j]+d[i][j-1].

C(a[i]+a[j]+b[i]+b[j],a[i]+a[j])可以看作:
(0,0)到(a[i]+a[j],b[i]+b[j])的方案数.

枚举i和j是O(n^2)的,显然要优化,
尝试将i和j分开:
将坐标位移一下变为(-a[i],-b[i])到(a[j],b[j])的方案数.
这样i和j就分离了,然后就可以单独计算每个部分的贡献.

观察前面的dp方程,我们一开始令d[0][0]=1,
然后计算出的d[x][y]就是(0,0)到(x,y)的方案数,
那么我们令d[-a[i]][-b[i]]=1,
那么计算出的d[x][y]就是(-a[i],-b[i])到(x,y)的方案数.
这样的话,我们一开始只需要令所有的d[-a[i]][-b[i]]++,
那么计算出来的d[x][y]就是所有数对到达(x,y)的方案数.
因此最后只需要累加d[a[i]][b[i]]即可.
但是存在(-a[i],-b[i])到(a[i],b[i])的方案数,也就是自己和自己匹配,
而题目只需要计算i<j的,因此减掉自己和自己匹配的,方案数为C(2*(a[i]+b[i]),2*a[i]).
最后答案还要再除以2,因为是计算出的是无序的,题目要的是有序的.

参考:
https://www.luogu.com.cn/blog/Ebola-Emperor/solution-at1983
https://www.luogu.com.cn/blog/208529/solution-at1983
*/


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

int main() {
  int n;cin>>n;
  vector<int> a(n+1);
  ll ans = 0;
  // 連想配列を使う map
  map<int,int> mp;
  for(int i=1; i<=n; i++) {
    cin>>a[i];
    if(i-a[i]>0) ans+=mp[i-a[i]];
    mp[i+a[i]]++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 14276
n, m = map(int, input().split())
A = list(map(int,input().split()))




total = sum(A)
A.sort(reverse = True)


judge = True

for i in range(m):
    if (total / (4*m)) <= A[i]:
        continue
    else:
        judge = not judge
        break

if judge:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.next());
    int x[] = new int[n];
    int c[] = new int[n];
    int t = 0;
    int min = 1000000000;
    int p = 0;
    
    for(int i=0; i<n; i++){
      x[i] = Integer.parseInt(sc.next());
    }
    
    for(int i=1; i<=100; i++){
      t = 0;
      for(int j=0; j<n; j++){
        t += (i-x[j])*(i-x[j]);
      }
      if(t<min) {
        min = t;
      }
    }
    
    System.out.println(min);
    
  }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

vector<string> num;
void dfs(int n, int m, string res){
  if(n == 0){
    num.push_back(res);
    return;
  }
  for(char c = res.back(); c <= m+'0'; c++){
    dfs(n-1,m,res+c);
  }
}

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n,m,q; cin >> n >> m >> q;
  vi a(q),b(q),c(q),d(q);
  rep(i,q) cin >> a[i] >> b[i] >> c[i] >> d[i];

  dfs(n,m,"1");
  int ans = 0;
  rep(i,num.size()){
    int res = 0;
    rep(j,q){
      if(num[i][b[j]]-num[i][a[j]] == c[j]) res += d[j];
    }
    chmax(ans,res);
  }
  cout << ans;
  cout << "\n";
  return 0;
}


Measured memory_bytes: 7380
#include <bits/stdc++.h>
using namespace std;
int n,m,x;
int main(){
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		n-=x;
	}
	
	if(n<0)printf("-1\n");
	else printf("%d\n",n);
	
	return 0;
} 

Measured memory_bytes: 3824
import Control.Monad (replicateM,foldM)
import Data.Array.IO (IOArray,readArray,writeArray,newListArray)

data CalcState = CalcState {
    maximumSum :: Int,
    currentSum :: Int,
    queue :: IOArray Int Int,
    queueLength :: Int,
    queueEnd :: Int
}

main = do
    [n,k] <- getLine >>= return . map read. words
    if all (==0) [n,k] then return () else do
        state <- replicateM k (getLine >>= return . read) >>= setup
        state <- foldM update' state [k+1..n]
        print (maximumSum state)

        main

    where
    update' state _ = getLine >>= return . read >>= update state


setup :: [Int] -> IO CalcState
setup ns = do
    let
        ql = length ns
        s = sum ns
    q <- newListArray (0,ql-1) ns
    return (CalcState s s q ql 0)

update :: CalcState -> Int -> IO CalcState
update (CalcState ms cs q ql qe) n = do
    r <- readArray q qe
    writeArray q qe n
    let
        cs' = cs - r + n
    return (CalcState (max ms cs') cs' q ql ((qe+1)`mod`ql))

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

int main() {
  uint64_t N;
  cin >> N;
  uint64_t a, b;
  a = (N/500)*1000;
  b = ((N%500)/5)*5;
  cout << a + b << endl;
}


Measured memory_bytes: 256
def is_palindrome(str)
  0.upto(str.size / 2) do |i|
    return false if str[i] != str[-i-1]
  end
  true
end

s = gets.strip

result = is_palindrome(s) && is_palindrome(s[0..s.size/2-1]) && is_palindrome(s[s.size/2+1..-1])
print result ? 'Yes' : 'No'

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

int main() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<P> qu(q);
    rep(i,q) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        qu[i] = make_pair(l,r);
    }
    vector<int> accu(n+1);
    accu[0] = 0;
    accu[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (s[i-1] == 'C' && s[i-2] == 'A') {
            accu[i] = accu[i-1] + 1;
        }
        else accu[i] = accu[i-1];
    }
    rep(i,q) {
        cout << accu[qu[i].second+1] - accu[qu[i].first+1] << endl;
    }
}

Measured memory_bytes: 2176
import sys,bisect
input = sys.stdin.readline

n = int(input())
dg = 10**10
mod = 998244353
xd = []

for i in range(n):
    x,d = map(int,input().split())
    xd.append((x+10**9)*dg + d)

xd.sort()

dp = [0]*(n+1)
ma = list(range(n+1))

def init_max(init_max_val):
    #set_val
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    #built
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
    
def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res

#####単位元######
ide_ele_max = -1

#num_max:n以上の最小の2のべき乗
num_max =2**(n-1).bit_length()
seg_max=[ide_ele_max]*2*num_max

init_max(ma)

dp[n] = 1


for i in range(n-1,-1,-1):
    x,d = xd[i]//dg,xd[i]%dg
    k = bisect.bisect_left(xd,(x+d)*dg)
    
    ma[i] = query_max(i,k)
    update_max(i,ma[i])
    
    dp[i] = (dp[i+1]+dp[ma[i]+1])%mod

print(dp[0]%mod)

Measured memory_bytes: 101340
// Problem : D - Simple Knapsack
// Contest : AtCoder - AtCoder Beginner Contest 060
// URL : https://atcoder.jp/contests/abc060/tasks/arc073_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}
map<pii,int> mp;
int n,w;
vp v;
int fun(int i,int j)
{
	if(j>w) return INT_MIN;
	if(i==n)return 0;
	if(mp.count({i,j}))return mp[{i,j}];
	return mp[{i,j}]=max2(fun(i+1,j),fun(i+1,j+v[i].f)+v[i].se);
}
void solve()
{
cin>>n>>w;
incd(v,n);
cin>>v;
cout<<fun(0,0);
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


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

int main(){
	string pass;
	cin >> pass;
	int l = pass.length(), n = 0, A = 0, a = 0;
	for(int i = 0; i < l; i++){
		if(isdigit(pass[i]) != 0){
			n = 1;
		}
		if(isupper(pass[i]) != 0){
			A = 1;
		}
		if(islower(pass[i]) != 0){
			a = 1;
		}
	}
	
	if(l >= 6 and n == 1 and A == 1 and a == 1){
		cout << "VALID" << endl;
	}
	else{
		cout << "INVALID" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define chmin(x,y) x = min(x,y)
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

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

    vector<int> a(M), b(M);
    vector<ll> c(M);

    rep(i, M) {
        cin >> a[i] >> b[i] >> c[i];
        a[i] = a[i] - 1;
        b[i] = b[i] - 1;
        c[i] = -c[i];
    }

    vector<ll> dist(N);
    rep(i, N) dist[i] = LINF;
    dist[0] = 0;

    rep(loop, N-1) {
        rep(i, M) {
            if (dist[a[i]] == LINF) continue;
            if (dist[b[i]] > dist[a[i]] + c[i]) dist[b[i]] = dist[a[i]] + c[i];
        }
    } 
    ll ans = dist[N-1];

    vector<bool> negative(N);
    rep(i, N) negative[i] = false;
    rep(loop, N) {
        rep(i, M) {
            if (dist[a[i]] == LINF) continue;
            if (dist[b[i]] > dist[a[i]] + c[i]) {
                dist[b[i]] = dist[a[i]] + c[i];
                negative[b[i]] = true;
            }
            if (negative[a[i]] == true) negative[b[i]] = true;
        }
    }

    if (negative[N-1])
    	cout << "inf" << endl;
    else
    	cout << -ans << endl;
	return 0;
}


Measured memory_bytes: 256
use proconio::input;

#[allow(unused_variables)]
fn main() {
    input! {
      n: usize, m: usize, c: isize,
      ba: [isize; m],
      mut aa: [[isize; m]; n]
    };

    let mut ans = 0;

    for i in 0..n {
        let mut sum = 0;
        for j in 0..m {
            sum += &aa[i][j] * &ba[j];
        }

        if sum + c > 0 {
            ans += 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 2144
n=int(input())
b=list(map(int,input().split()))
summ=0
summ+=b[0]
for i in range(n-2):
    if b[i+1]<=b[i]:
        summ+=b[i+1]
    elif b[i+1]>b[i]:
        summ+=b[i]
summ+=b[n-2]
print(summ)    

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())


int main() {
    int n;
    cin >> n;
    vector <pair<string, pair<int, int> > > vec;

    repn(i, n) {
        string s;
        int a;
        cin >> s >> a;
        vec.push_back(make_pair(s, make_pair(-a, i)));
    }
    sort(vec.begin(), vec.end());
    rep(i, n)
        cout << vec[i].second.second << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int maxn=1010;
ll n,T[maxn],A[maxn];
int main()
{
	cin>>n;
	ll cnt1=1,cnt2=1;
	for(int i=0;i<n;i++)
	{
		cin>>T[i]>>A[i];
		if(T[i]==A[i])
		{
			cnt1=cnt2=max(cnt1,cnt2);
		}
		else
		{
			if(T[i]>=cnt1&&A[i]>=cnt2)
			{
				cnt1=T[i];
				cnt2=A[i];
				continue;
			}
			long long a=(cnt1+T[i]-1)/T[i],b=(cnt2+A[i]-1)/A[i];
			cnt1=T[i]*max(a,b);
			cnt2=A[i]*max(a,b);
		}
	}
	cout<<cnt1+cnt2<<endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())

def yakusuu(num):
	count = 0
	for i in range(1,num+1):
		if num%i==0:
			count+=1
	return count


ans=0
ns = [x for x in range(1,n+1) if x%2==1]
for j in ns:
	if yakusuu(j)==8:
		ans+=1

print(ans)

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(void){
  int a, b;
  string op;
  while(1){
      cin>> a >> op >>b;
      if(op=="+"){
          cout<< a+b <<endl;
      } else if(op=="-"){
          cout<< a-b <<endl;
      } else if(op=="*"){
          cout<< a*b <<endl;
      } else if(op=="/"){
          cout<< a/b <<endl;
      } else{
          break;
      }
  }      
}


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

int main(){
    std::string N;
    std::cin >> N;
    
    int sum = 0;
    for(int i=0; i<(int)N.size(); i++){
        sum += N[i] - '0';
    }
    
    if(sum % 9 == 0){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    
    
    return 0;
    
}


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

using namespace std;
int main(){
	int color[100] = { 0 };
	int a, b, c, res = 0;
	cin >> a >> b >> c;

	color[a-1] = 1;
	color[b-1] = 1;
	color[c-1] = 1;
	
	for(int i=0; i<100; i++) if(color[i]) res += 1;

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n, q, a, b, x, y;
    cin >> n >> q;
    vector<vector<int>> tree(n, vector<int>(0));
    rep(i, n - 1) {
        cin >> a >> b;
        a--;
        b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    vector<int> c(n, 0);
    rep(i, q) {
        cin >> x >> y;
        c[x - 1] += y;
    }
    vector<bool> is_visited(n, false);
    queue<int> qu;
    qu.push(0);
    is_visited[0] = true;
    while (!qu.empty()) {
        int top = qu.front();
        qu.pop();
        for (auto o : tree[top]) {
            if (is_visited[o] == false) {
                c[o] += c[top];
                is_visited[o] = true;
                qu.push(o);
            }
        }
    }
    rep(i, n) {
        if (i != n - 1)
            cout << c[i] << ' ';
        else
            cout << c.back() << endl;
    }
}

Measured memory_bytes: 16500
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 20 20:52:23 2019

@author: Owner
"""

import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*M
Y = [0]*M
for m in range(M):
    P[m], Y[m] = map(int, input().split())
    
all(nstr.count(c) for c in '753')
"""
N = int(input())

h = [0]*N
h[:] = map(int, input().split())

h = np.array(h)

cnt = 0
while np.sum(h ==0) != N:
    if np.sum(h ==0) == 0:        
        h = h-1
        cnt +=1
    else:
        r=N-1
        for n in range(N-1):
            if h[n] == 0 and h[n+1] !=0:
                l = n+1
            elif h[0] != 0:
                l = 0
            else:
                pass
            if h[n] != 0 and h[n+1] == 0:
                r = n
                break
        for x in range(l, r+1):
            h[x] = h[x] -1
        cnt +=1
print(cnt)
            
            
            
        
            


Measured memory_bytes: 15192
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
using namespace std;

int main(){
    double w,h;
    int x,y;
    cin >> w >> h >> x >> y;

    int c;

    if(x == w/2 && y == h/2){
        c = 1;
    } else {
        c = 0;
    }

    cout << w*h/2 << " " << c << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define INF 10000000

void dfs();
int dp[100000];
int t[16][17];
int N;

int main(){
  while(cin >> N , N){
    for(int i=0;i<N;i++){
      for(int j=0;j<N+1;j++){
	cin >> t[i][j];
      }
    }
    dfs();
  }
}

void dfs(){
  int to = (1<<N);
  for(int i=0;i<to;i++){
    dp[i] = INF;
  }
  dp[0] = 0;
  for(int next=0;next<to;next++){
    if(dp[next] == INF) continue;
    for(int i=0;i<N;i++){
      int cost = t[i][0];
      if((next & (1 << i)) != 0) continue;
      for(int j=0;j<N;j++){
	if((next & (1 << j)) != 0){
	  cost = min(cost,t[i][j+1]);
	}
      }
      int bit = (next | (1 << i));
      dp[bit] = min(dp[bit],dp[next]+cost);
    }
  }
  cout << dp[to-1] << endl;
}

Measured memory_bytes: 1416