akhauriyash/Code-Regression huggingface dataset:
n,a,b = map(int,input().split())

if (b - a) % 2 == 0:
    ans = (b - a) //2
else:
    x = b - 1
    y = n - a
    w = n - b
    z = a - 1
    ans = min((y+w+1)//2,(x+z+1)//2)
print(ans)


Measured memory_bytes: 2940
#![allow(unused)]
use std::cmp;
use std::io;

fn main() {
    println!("{}", solve());
}

pub fn solve() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    let n: i64 = iter.next().unwrap().parse().unwrap();
    let k: i64 = iter.next().unwrap().parse().unwrap();

    let t = n % k;
    let t2 = k - t;
    format!("{}", cmp::min(t, t2))
}

Measured memory_bytes: 4352
import Data.List
import Data.Bits
import qualified Data.ByteString.Char8 as BS

readInt s = case BS.readInt s of
              Just (x, _) -> x

main = do
  _n <- readInt <$> BS.getLine
  a <- foldl' (.|.) 0 . map readInt . BS.words <$> BS.getLine
  print $ countTrailingZeros a


Measured memory_bytes: 508
#include<bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    vector<double> v(N);
    REP(i,N) cin >> v[i];
    sort(v.begin(), v.end());
    double ans;
    REP(i,N-1){
        if (i == 0){
            ans = (v[i] + v[i+1]) / 2;
        }else{
            ans = (ans + v[i+1]) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>

using namespace std;

int main()
{
    char s[1000000];
    cin >> s;
    int length=strlen(s);
    for(int i=0; i<(length+1)/2; i++){
        cout << s[i*2];
    }
    
    return 0;
}

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

long long a,b;

long long gcd(long long a,long long b){
  if(b == 0) 
    return a;
  else 
    return gcd(b, a % b);
}
long long lcm(long long a,long long b){
    return (a * b) / gcd(a, b);
}

int main(){
  while(cin >> a >> b){
    cout << gcd(a ,b) << " " << lcm(a, b) << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
<?php
//$N = (int)trim(fgets(STDIN));
//$S = trim(fgets(STDIN));
//list($A,$B) = array_map('intval',explode(" ",trim(fgets(STDIN))));
list($A,$B) = explode(" ",trim(fgets(STDIN)));
//$A = array_map('intval',explode(" ",trim(fgets(STDIN))));


printf("%d\n",bcmul($A,$B));


Measured memory_bytes: 16168
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t x,y;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> x>>y;
	out << x + y / 2 << endl;

	return 0;
}
#endif


Measured memory_bytes: 888
ROOT = 3
MOD = 998244353
pn = [pow(ROOT,(MOD-1)>>i,MOD) for i in range(30)]

def ntt_rec(a,n):
    if n==0:
        return a[:]
    if n==1:
        return [a[0]+a[1],a[0]-a[1]]

    b = ntt_rec(a[::2],n-1)
    c = ntt_rec(a[1::2],n-1)
    
    N = 1<<(n-1)
    res = [0]*(N*2)
    w_N = 1
    for k in range(N):
        res[k]   = (b[k] + w_N*c[k])%MOD
        res[k+N] = (b[k] - w_N*c[k])%MOD
        w_N = w_N*pn[n]%MOD
    return res

def intt_rec(a,n):
    res = ntt_rec(a[0:1]+a[1:][::-1],n)
    inv = pow(1<<n,MOD-2,MOD)
    for i in range(1<<n):
        res[i] = res[i]*inv%MOD
    return res


def convolution(a,b):
    deg = len(a) + len(b) - 1
    n = 0
    N = 1
    while deg*2 >= N:
        n += 1
        N <<= 1
    
    a += [0]*(N-len(a))
    b += [0]*(N-len(b))
    
    #print(ntt_rec(a,n))
    return intt_rec([ai*bi%MOD for ai,bi in zip(ntt_rec(a,n),ntt_rec(b,n))],n)

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
#*a, = [1]*10**5
#*b, = [1]*10**5
L = len(a)+len(b)
c = convolution(a,b)
print(*c[:L-1])


Measured memory_bytes: 343380
S = input()
N = len(S)

increasing = S[0] == '<'
A = [] if increasing else [1]
cnt = 0
for c in S:
    f = c == '<'
    if f == increasing:
        cnt += 1
    else:
        A.append(cnt*(increasing*2-1))
        increasing = not increasing
        cnt = 1
A.append(cnt*(increasing*2-1))

if A[-1] > 0:
    A.append(-1)

m = iter(A)
res = 0

for a,b in zip(m,m):
    b = -b
    if a > b:
        a,b = b,a
    res += ((a-1)*a+(b+1)*b)

print(res//2)

Measured memory_bytes: 84932
object Main extends App {
    val scanner = new java.util.Scanner(System.in)
    val a = scanner.next().toInt
    val b = scanner.next().toInt
    val k = scanner.next().toInt
    val ma = math.max(a, b)
    val mi = math.min(a, b)
    for (i <- mi to (math.min(mi+k, ma)-1)) println(i)
    for (i <- math.max(math.min(mi+k, ma)-1, ma-k)+1 to ma) println(i)
}


Measured memory_bytes: 25656
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void p754() {
	string s;
	cin >> s;
	int res = 1000;
	for (size_t i = 0; i < s.size() - 2; i++)
	{
		int a = stoi(s.substr(i, 3));
		res = min(res, abs(753 - a));
	}
	cout << res << endl;
}
int main() {

	p754();
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string s = Console.ReadLine();
		long[]A = new long[2019];
		long ans = 0;
		int a1 = 0;
		int d1 = 1;
		A[0] = 1;
		for(var i=s.Length-1;i>=0;i--){
			int a = int.Parse(s.Substring(i,1));
			a1 = (a * d1 + a1) % 2019;
			A[a1]++;
			ans += A[a1]-1;
			d1 = (d1 * 10) % 2019;
			//Console.Error.WriteLine(a1);
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 21680
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
#import numpy as np
def main():
    n = int(input())
    if n == 1:
        print(1)
        sys.exit()
    r = 0
    for i1 in range(1, n + 1):
        num_of_div = n // i1
        r += num_of_div * (num_of_div + 1) // 2 * i1
    print(r)

if __name__ == '__main__':
    main()


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


int main(){
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    ans += (n - m) * 100 + m * 1900;
    ans *= ll(pow(2,m));
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(I,X,Y) for(long long (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(long long (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define pb push_back
#define COUNT(V,X) upper_bound((V).begin(),(V).end(),X)-lower_bound((V).begin(),(V).end(),X)
#define debug(x) cerr<<#x<<':'<<x<<endl;
#define DEBUG(v) cerr<<#v<<':';for(auto xXx:v)cerr<<xXx<<' ';cerr<<endl;
#define INF 1000000007
#define LINF 1000000000000000007
#define Yes(X) if(X){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YES(X) if(X){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define ctoi(C) (C-'0')
typedef long long ll;
typedef long double ld;
long long dx[] = {1,0,-1,0};
long long dy[] = {0,1,0,-1};
long long dx8[] = {1,1,0,-1,-1,-1,0,1};
long long dy8[] = {0,1,1,1,0,-1,-1,-1};
long long dx9[] = {1,1,0,-1,-1,-1,0,1,0};

signed main(){
    ll N,T;
    cin >> N >> T;
    ll imos[T+1] = {0};
    FOR(i,0,N){
        ll l,r;
        cin >> l >> r;
        imos[l]++;
        imos[r]--;
    }
    FOR(i,1,T+1)imos[i] += imos[i-1];
    cout << *max_element(imos,imos+T+1) << endl;
}


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

using namespace std;

#define inf (int)1e9
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;

const int N = 123456;
const int M = 1234567;

#define Cft C
#define Dft D

int Cft[N];
int Dft[N];

int query(int x, int t){

	int ans = 0;
	while(x){
		ans = max(ans, t ? C[x] : D[x]);
		x -= x & -x;
	}

	return ans;
}


void add(int x, int val, int t){

	while(x <= 123456){
		t? C[x] = max(C[x], val) : D[x] = max(D[x], val);
		x += x & -x;
	}
}

int main(int argc, char const *argv[])
{
	
	#ifdef Cyborg1o1
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif	

	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;

	cin >> n >> m;

	std::vector<int> c(n + 1, 0);

	while(m--){
		int a, b;
		cin >> a >> b;

		c[a]++;
		c[b]++;

	}

	for(int i = 1; i <= n; ++i){
		cout << c[i] << endl;
	}
	return 0;				
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        if(a+b<10)
        {
            cout<<a+b<<endl;
        }
        else if(a+b>=10)
        {
            cout<<"error"<<endl;
        }
    }
}


Measured memory_bytes: 256
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
k9=0
k6=0
for n in range(9,N+1):
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9+5;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

constexpr int mod = 1000000007;

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

  int n, W;
  cin >> n >> W;
  vector<int> w(n);
  vector<ll> v(n);
  rep(i, n) cin >> w[i] >> v[i];

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

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

  cout << dp[n][W] << endl;

  return 0;
}


Measured memory_bytes: 83060
//Volume1-0126
import java.util.Scanner;

class Main {
	public static void main(String[] args){

		final int L = 9;
		int [][] table;
		char[][] check;

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		while(n-- > 0){
			table = new int [L][L];
			check = new char[L][L];

			for(int i=0;i<L;i++){
				for(int j=0;j<L;j++){
					table[i][j] = sc.nextInt();
					check[i][j] = ' ';
				}
			}

			for(int i=0;i<L;i++){
				for(int j=0;j<L;j++){
					for(int k=j+1;k<L;k++){
						if(table[i][j]==table[i][k]){
							check[i][j] = '*';
							check[i][k] = '*';
						}
						if(table[j][i]==table[k][i]){
							check[j][i] = '*';
							check[k][i] = '*';
						}
						if(table[i/3*3+j/3][i%3*3+j%3]==table[i/3*3+k/3][i%3*3+k%3]){
							check[i/3*3+j/3][i%3*3+j%3] = '*';
							check[i/3*3+k/3][i%3*3+k%3] = '*';
						}
					}
				}
			}

			for(int i=0;i<L;i++){
				for(int j=0;j<L;j++){
					System.out.print(check[i][j]);
					System.out.print(table[i][j]);
				}
				System.out.println();
			}
			if(n>0){System.out.println();}
		}
	}
}

Measured memory_bytes: 23340
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(8)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bitcount _builtin_popcount
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
using namespace __gnu_pbds;
using namespace std;
//typedef
typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;
typedef vector<pair<int,int> > vii;
typedef vector<int> vi;
typedef pair<int,int> ii;
//constants
const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;
//
#define forn(i, n)for(ll i=0;i<n;i++)
// gcd of a and b
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
// distance between (a,b) and (c,d)
long double dis(long long a,long long b,long long c,long long d){return sqrt( ((a)-(c))*((a)-(c))+((b)-(d))*((b)-(d)) );}
// simple prime check
bool isprime(long long a){
if(a==2)return 1;
if(!(a&1))return 0;
for(ll i=3;i*i<=a;i+=2){
	if(a%i==0)return 0;
}
return 1;
}
// fast expo
long long mpow(long long base,long long exponent,long long modulus){
if(modulus==1)return 0;
long long result = 1;
base=base%modulus;
while(exponent){
		if(exponent%2 == 1)
			result=(result*base)%modulus;
		exponent=exponent>>1;
		base=(base*base)%modulus;
	}
return result;
}
// modular inverse
ll minv(ll a,ll mod){
	ll _gcd=gcd(a,mod);
	assert(_gcd==1);
	return mpow(a,mod-2,mod);
}

/*
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

/*
ll dx[]={1,0,-1,0,1,1,-1,-1};
ll dy[]={0,-1,0,1,1,-1,-1,1};
*/

/*
void sieve(int N){
	for(int i=0;i<=N;i++){
		spf[i]=i;
	}
	for(int i=2;i*i<=N;i++){
		if(spf[i]==i){
			for(ll j=i*i;j<=N;j+=i){
				spf[j]=min(spf[j],i);
			}
		}
	}
	return;
}
*/

/*
void nCr(ll n,ll k){
	ll i,j;
	for(i=0;i<=n;i++){
		for(j=0;j<=min(i,k);j++){

			if(j==0 or j==i)C[i][j]=1LL;
			else  C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;

		}
	}
	return;
}
*/
/*
ll ncr(ll N,ll K){
	if(N<K)return 0;
	if(K==0)return 1;
	if(N==0)return 0;

	ll den=1;
	for(ll i=1;i<=K;i++)den*=i;
	ll num=1;
	while(K--){
		num*=N;
		if(num%den==0){
			num/=den;
			den=1;
		}
		N--;
	}

	return num;
}
*/

ll n;
ll a[100005];
ll sum;
int main(){FAST;
cin>>n;
for(ll i=1;i<=n;i++){
	cin>>a[i];
	sum+=abs(a[i]);
}
ll ct =0 ;
for(ll i=1;i<=n;i++){
	if(a[i]<0){
		ct++;
	}
}

ll mi = abs(a[1]);
for(ll i=1;i<=n;i++){
	mi=min(mi,abs(a[i]));
}

if(ct&1){
	cout<<sum-2*mi;
}
else{
	cout<<sum;
}
return 0;
}




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

// 插入此處
const LL mod = 1000000007;

int main() {
	int n; cin >> n;
	string s1, s2;
	cin >> s1 >> s2;
	vector<int> patt;
	for (int i = 0; i < n; ++i) {
		if (s1[i] == s2[i])  patt.push_back(0);
		else {
			patt.push_back(1);
			++i;
		}
	}
	LL ans = 1;
	for (int i = 0; i < patt.size(); ++i) {
		if (patt[i] == 0) {
			if (i == 0) {
				ans *= 3;
			} else {
				if (patt[i-1] == 0) {
					ans = ans * 2 % mod;
				} else {
					ans = ans;
				}
			}
		} else {
			if (i == 0) {
				ans *= 6;
			} else {
				if (patt[i-1] == 0) {
					ans = ans * 2 % mod;
				} else {
					ans = ans * 3 % mod;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
    string S;
    cin >> S;

    for (size_t i = 0; i < S.size() / 2; i++)
    {
        if (S[i] != S[S.size() - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    ll N = S.size();
    for (size_t i = 0; i < N / 2; i++)
    {

        if (S[i] != S[N / 2 - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    for (size_t i = N / 2; i < N; i++)
    {
        if (S[i] != S[N - 1 - i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 5005;
const lli inf = 1e18;
int n;
pii x[maxn];

lli dp[maxn][maxn];

bool cmp(const pii&p, const pii&q)
{
    return p.first + p.second < q.first + q.second;
}

void read_input()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> x[i].first >> x[i].second;
    sort(x + 1, x + n + 1, cmp);
}

void minim(lli&tar, lli val)
{
    if(tar > val) tar = val;
}

void solve()
{
    fill_n(&dp[0][0], sizeof(dp) / sizeof(dp[0][0]), inf);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j < i; ++j)
        {
            minim(dp[i][j], dp[i - 1][j]);
            if((lli)x[i].first >= dp[i - 1][j])
                minim(dp[i][j + 1], dp[i - 1][j] + (lli)x[i].second);
        }
    for(int j = n; j >= 0; --j)
        if(dp[n][j] != inf)
        {
            cout << j << '\n';
            break;
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}


Measured memory_bytes: 196096
n = int(input()) % 26
s = input()
res = ''
for i in s:
    if i.islower():
        c = chr(ord(i) + n)
        res += c if c.islower() else chr(ord(c) - 26)
    elif i.isupper():
        c = chr(ord(i) + n)
        res += c if c.isupper() else chr(ord(c) - 26)
    else:
        res += i
print(res)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    ll sum = 0;
    for(int i = 1; i <= n; ++i)
        if(i%3 == 0 || i%5 == 0);
        else
            sum += i;
    cout << sum;
    return 0;
}


Measured memory_bytes: 3584
from math import factorial as f
N, M = sorted(list(map(int, input().split())))

MOD = 10**9 + 7
gap = M - N
if gap >= 2:
	ans = 0
else:
	ans = f(M) * f(N)
	if gap == 0:
		ans *= 2 % MOD
print(ans % MOD)

Measured memory_bytes: 5184
n, m = map(int, input().split())


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
            # if (1 << (sw - 1)) & bits: # こちらの判定でも良い
                cnt += 1
        if cnt%2 != lst_p[i]:
            judge = False
    if judge:
        ans += 1


print(ans)


Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <stack>
#include <string>
#include <cmath>
#define SIZE 55

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll A[SIZE];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&A[i]);
	vector <P> ans;
	P mx=P(A[0],0),mn=mx;
	for(int i=0;i<n;i++) mx=max(mx,P(A[i],i)),mn=min(mn,P(A[i],i));
	if(mx.first+mn.first>=0)
	{
		for(int i=0;i<n;i++)
		{
			if(i==mx.second) continue;
			ans.push_back(P(mx.second,i));
			A[i]+=mx.first;
		}
		for(int i=0;i+1<n;i++) ans.push_back(P(i,i+1));
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(i==mn.second) continue;
			ans.push_back(P(mn.second,i));
			A[i]+=mx.first;
		}
		for(int i=n-1;i>=1;i--) ans.push_back(P(i,i-1));
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++)
	{
		P p=ans[i];
		printf("%d %d\n",p.first+1,p.second+1);
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int max = sc.nextInt();
    int cnt = 1;
    for (int i = 0; i < N - 1; i++) {
      int A = sc.nextInt();
      if (max <= A) {
        max = A;
        cnt++;
      }
    }
    System.out.println(cnt);
  }
}


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

int main()
{
	string S;
	cin >> S;
	const int N = S.size();
	int res = N;
	for (int i = 1; i < N; i++) {
		if (S[i - 1] == S[i]) {
			--res;
			i += 2;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 640
from functools import reduce
def mycmb(n,r,p):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(lambda x,y:x*y%p,range(n,n-r,-1))
    under = reduce(lambda x,y:x*y%p,range(1,r+1))
    return (over * pow(under,p-2,p))%p
    

n,a,b = map(int,input().split())
p = 10**9 + 7

syu = pow(2,n,p) - 1 - mycmb(n,a,p) - mycmb(n,b,p)
print(syu%p)

Measured memory_bytes: 9584
#include<iostream>
using namespace std;
int main(){
  int n=3;
  int N[n];
  int r[n]={5,7,5};
  int t[n];
  for(int i=0;i<n;i++){
    cin>>N[i];
  }
  int five=0;
  int seven=0;
  for(int i=0;i<n;i++){
    if(N[i]==5){
      five++;
    }
    if(N[i]==7){
      seven++;
    } 
  }
  
  if(five==2&&seven==1) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
 return 0; 
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int r,c,t;
    t=0;
    cin>>r>>c;
    int R[c+1]={};
    int S[c+1]={};
    for (int i=0;i<r;i++){
        for(int x=0;x<c;x++){
            cin>>R[x];
            cout<<R[x]<<" ";
        }
        for(int x=0;x<c;x++){
            t+=R[x];
        }
    cout<<t<<endl;
    for(int b=0;b<c;b++){
        S[b]+=R[b];
    }
    R[c+1]={};
    t=0;
    }
    for(int x=0;x<c;x++){
        cout<<S[x]<<" ";
        S[c]+=S[x];
    }
    cout<<S[c]<<endl;    
}



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

int main(){
	int w;
	while(cin >> w && w != -1){
		int c = 0;
		c += 1150;
		c += 125 * max(0,min(w-10,10));
		c += 140 * max(0,min(w-20,10));
		c += 160 * max(0,w-30);
		cout << 4280 - c << endl;
	}
}

Measured memory_bytes: 0
n, c, k = map(int, input().split())
t = [int(input()) for _ in range(n)]
t.sort()
ans = 0
i = 0
while i < n:
    ans += 1
    m = t[i]
    cnt = 0
    while i < n and m <= t[i] <= m + k and cnt < c:
        cnt += 1
        i += 1
print(ans)

Measured memory_bytes: 7384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication8
{
    class Program
    {
        static void Main(string[] args)
        {
            // 入力
            string strInputData = Console.ReadLine();

            // 出力
            foreach(char charcter in strInputData)
            {
                if (Char.ToLower(charcter) == charcter)
                {
                    Console.Write(Char.ToUpper(charcter));
                }
                else
                {
                    Console.Write(Char.ToLower(charcter));
                }
            }

            Console.Write("\r\n");
        }
    }
}



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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    ll X;
    cin >> X;
    ll cur = 100;
    ll ans = 0;
    while (cur < X) {
        cur += cur / 100;
        ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

char s[55];
int n,k;

int main(){
  	scanf("%d%d",&n,&k);
  	scanf("%s",&s);
  	s[k-1] = tolower(s[k-1]);
  	printf("%s\n",s);
	return 0;
}

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

struct {
	char suit;
	int value;
}typedef Card;

void swap(Card *a, Card *b){
	Card work;
	work = *a;
	*a = *b;
	*b = work;
}

void BubbleSort(Card c[],int n){
	for(int i=0;i<n;i++){
		for(int j=n-1;j>=i;j--){
			if(c[j].value < c[j-1].value){
				swap(&c[j],&c[j-1]);
			}
		}
	}
}

void SelectionSort(Card c[],int n){
	int minj;
	for(int i=0;i<n;i++){
		minj=i;
		for(int j=i;j<n;j++){
			if(c[j].value < c[minj].value) minj = j;
		}
		swap(&c[i],&c[minj]);
	}
}

bool isStable(Card c1[], Card c2[],int n){
	for(int i=0;i<n;i++){
		if(c1[i].suit != c2[i].suit) return false;
	}
	return true;
}

void printCards(Card c[],int n){
	for(int i=0;i<n;i++){
		if(i>0) cout << " ";
		cout << c[i].suit << c[i].value;
	}
	cout << endl;
}

int main(){
	Card c1[100],c2[100];
	int n;
	cin >> n;
	for(int i=0;i<n;i++) cin >> c1[i].suit >> c1[i].value;

	//copy c1 to c2
	for(int i=0;i<n;i++){
		c2[i] = c1[i];
	}

	BubbleSort(c1,n);
	SelectionSort(c2,n);

	printCards(c1,n);
	cout << "Stable" << endl;
	printCards(c2,n);
	if(isStable(c1,c2,n)) cout << "Stable" << endl;
	else cout << "Not stable" << endl;

	return 0;
}

Measured memory_bytes: 1164
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = S()
ans = list()
for c in N:
    if c == '1':
        ans.append('9')
    else:
        ans.append('1')
print(''.join(ans))

Measured memory_bytes: 38640
li=list(map(int,input().split()))
n=li[0]
y=li[1]

a,b,c=-1,-1,-1

for i in range(n+1):
    for j in range(n-i+1):
        if y==10000*i+5000*j+1000*(n-i-j):
            a=i
            b=j
            c=n-i-j
            break
print(a,b,c)


Measured memory_bytes: 3060
/*input
2
ip cc
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define eb emplace_back
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define EL cout<<'\n'
#define BS(a,x) binary_search(ALL(a),x)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
	REP(i,SZ(V)) out<<V[i]<<((i!=SZ(V)-1)?" ":"");
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=20;
const ll INF64=1e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}


int main(){
	IOS;
	string s;
  cin>>s;
  sort(ALL(s));
  if(s[0]==s[1]&&s[1]!=s[2]&&s[2]==s[3]) cout<<"Yes\n";
  else cout<<"No\n";
       return 0;
}


Measured memory_bytes: 256
//“Failure is unimportant. It takes courage to make a fool of yourself.”

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
#define int long long int
#define P 1000000007
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define b(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 1000
#define PI 3.14159265359
#define inf LLONG_MAX
using namespace __gnu_pbds;
using namespace std;

signed main() {
    teevra_gati
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll flg=1, cnt=1;
    while(a>0 && c>0){
        if(cnt&1){
            c-=b;
            if(c<=0){
                cout<<"Yes";
                return 0;
            }
        }
        else{
            a-=d;
            if(a<=0){
                cout<<"No";
                return 0;
            }
        }
        cnt++;
    }
    return 0;
}


Measured memory_bytes: 3584
/**
 * code generated by Junayed Kader
 * Student of Computer Science
 * @author
 */

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu ()
{
    cerr << endl;
}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest)
{
    cerr << arg << ' ';
    faltu(rest...);
}

ll gcd ( ll a, ll b )
{
    return __gcd ( a, b );
}
ll lcm ( ll a, ll b )
{
    return a * ( b / gcd ( a, b ) );
}
ll max(ll a,ll b)
{
    return a>b?a:b;
}
ll min(ll a,ll b)
{
    return a<b?a:b;
}
const int mx = 1e5+123;
int dp[mx], n,k, stone[mx];
int solve (int i )
{
    if(i==n) return 0;
    if(dp[i]!=-1) return dp[i];

    int   ret = inf;

    for(int j = 1;j<=k; j++){
    if(i+j<=n) ret = min (ret,  abs(stone[i]-stone[i+j])+solve(i+j));

    }
     return dp[i] = ret;

}
void _case()
{


   cin>>n>>k;
   for(int i = 1; i<=n;i++)
   {
       cin>>stone[i];
   }
   mem(dp, -1);
   cout<<solve(1)<<endl;


}
int main()
{
    optimize();
     _case();

    return 0;
}


Measured memory_bytes: 12224
# https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_b

n = int(input())
nums = [int(i) for i in input().split()]

ans = 0
d = set()
for i in range(n):
    a = i + 1
    b = nums[i]
    if (a, b) in d or (b, a) in d:
        ans += 1
    else:
        d.add((a, b))
        d.add((b, a))
print(ans)


Measured memory_bytes: 70000
import java.util.Scanner;

/**
 * String Formation
 * 
 * https://atcoder.jp/contests/abc158/tasks/abc158_d
 */
public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) throws Exception {
        String S = sc.next();
        int Q = sc.nextInt();

        boolean order = true;
        StringBuilder prefix = new StringBuilder();
        StringBuilder suffix = new StringBuilder();

        for (int i = 0; i < Q; i++) {
            int T = sc.nextInt();

            if (T == 1) {
                order = !order;
            } else {
                int F = sc.nextInt();
                String C = sc.next();

                if ((F == 1 && order) || (F == 2 && !order)) {
                    prefix.append(C);
                } else {
                    suffix.append(C);
                }
            }
        }

        StringBuilder ans = new StringBuilder();
        ans.append(prefix.reverse());
        ans.append(S);
        ans.append(suffix);

        if (order) {
            System.out.println(ans.toString());
        } else {
            System.out.println(ans.reverse().toString());
        }
    }

}


Measured memory_bytes: 125220
#include <iostream>

using namespace std;

int min(int x, int y, int z) 
{ 
    return min(min(x, y), z); 
}

int dp(string x,string y, int m) 
{ 
    int count(0);
    for (int i = 0; i <= m; i++) { 
        if (x[i] != y[i]) count++;
    }
    return count;
} 

int main()
{
    string x,y;
    cin>>x>>y;
    cout<<dp(x,y,x.length());
}

Measured memory_bytes: 4048
#! -*- coding:utf-8 -*-

ans = [ [0, 0] for _ in xrange(4) ]

def get(x):
	if x >= 1.1: return 0
	if x >= 0.6: return 1
	if x >= 0.2: return 2
	return 3

while True:
	try:
		a, b = [ float(_) for _ in raw_input().split() ]
	except:
		break
	ans[get(a)][0] += 1
	ans[get(b)][1] += 1

for an in ans:
	print an[0], an[1]

Measured memory_bytes: 4248
N = int(input())
top_bottom = [[0]*10 for _ in range(10)]
for i in range(1, N + 1):
    s = str(i)
    top_bottom[int(s[0])][int(s[-1])] += 1
ans = 0
for i in range(1, 10):
    for j in range(1, 10):
        ans += top_bottom[i][j] * top_bottom[j][i]
print(ans)


Measured memory_bytes: 9128
def main():
    class UnionFind():
        # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
            def __init__(self, n):
                self.n = n
                # root[x]<0ならそのノードが根かつその値が木の要素数
                # rootノードでその木の要素数を記録する
                self.root = [-1]*(n+1)
                # 木をくっつける時にアンバランスにならないように調整する
                self.rnk = [0]*(n+1)      
            # ノードxのrootノードを見つける
            def Find_Root(self, x):
                if(self.root[x] < 0):
                    return x
                else:
                    # ここで代入しておくことで、後の繰り返しを避ける
                    self.root[x] = self.Find_Root(self.root[x])
                    return self.root[x]
            # 木の併合、入力は併合したい各ノード
            def Unite(self, x, y):
                # 入力ノードのrootノードを見つける
                x = self.Find_Root(x)
                y = self.Find_Root(y)
                # すでに同じ木に属していた場合
                if(x == y):
                    return 
                # 違う木に属していた場合rnkを見てくっつける方を決める
                elif(self.rnk[x] > self.rnk[y]):
                    self.root[x] += self.root[y]
                    self.root[y] =  x 
                else:
                    self.root[y] += self.root[x]
                    self.root[x] = y
                    # rnkが同じ（深さに差がない場合）は1増やす
                    if(self.rnk[x] == self.rnk[y]):
                        self.rnk[y] += 1
            # xとyが同じグループに属するか判断
            def isSameGroup(self, x, y):
                return self.Find_Root(x) == self.Find_Root(y)     
            # ノードxが属する木のサイズを返す
            def Count(self, x):
                return -self.root[self.Find_Root(x)]      
    #abc049D
    ii = lambda : int(input())
    mi = lambda : map(int,input().split())
    li = lambda : list(map(int,input().split()))
    n,k,l = mi()
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p,q = mi()
        road.Unite(p,q)
    for i in range(l):
        p,q = mi()
        train.Unite(p,q)
    lis = []
    for i in range(1,n+1):
        a = road.Find_Root(i)
        b = train.Find_Root(i)
        lis.append(a + 10 ** 6 * b)
    from collections import Counter
    z = Counter(lis)
    lis2 = []
    for i in range(n):
        lis2.append(z[lis[i]])
    print(*lis2)
       
main()
 

Measured memory_bytes: 37032
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned long;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

struct Problem {

    void Solve() {
        while (true) {
            UL N; cin >> N;
            if (N == 0) return;
            vector<double> D(N); rep(i, N) cin >> D[i];
            double A = 0; rep(i, N) A += D[i]; A /= N;
            double S = 0; rep(i, N) S += (D[i] - A) * (D[i] - A); S /= N;
            S = sqrt(S);
            cout << S << endl;
        }
    }
};
int main() {
    unique_ptr<Problem> p(new Problem());
    cout << fixed << setprecision(10);
    p->Solve();
    return 0;
}



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

class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
		String str="";
		String build="";
		str=bfr.readLine();
		int mojisu=str.length();
		StringBuilder sb=new StringBuilder();

		for(int i=0; i<mojisu; i+=2) {
			sb.append(str.charAt(i));
		}
		System.out.println(sb.toString());
	}
}

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

#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define unq(v) sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end())
#define ll long long
#define pb push_back
#define fill(arr) memset(arr,0,sizeof(arr))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define pi acos(-1.00)
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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



Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;
using ll = long long;

int N, M;
int dp[10001] = {};
vector<ll> A;
ll cost[] = {0,2,5,5,4,5,6,3,7,6};
string ans = "";
int tmp;
int Inf = 2 << 10;

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

    cin >> N >> M;

    for (int m = 0; m < M; ++m) {
        cin >> tmp;
        A.push_back(tmp);  
    }
    sort(A.begin(), A.end(), greater<int>());

    for (int n = 1; n <= N; ++n) {
        dp[n] = -Inf;
        for (auto e : A) {
            if (n >= cost[e])
                dp[n] = max(dp[n], dp[n - cost[e]] + 1);
        }
    }

    int remained = N;
    while (remained > 0) {
        for (auto e : A) {
            if (dp[remained - cost[e]] == dp[remained] - 1) {
                if (remained < cost[e]) continue;
                if (1 == dp[remained])
                    if (remained != cost[e]) continue;
                ans += to_string(e); 
                remained -= cost[e]; 
                break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
li = [ int(it) for it in input().split()]
li.sort()

import collections
col = collections.Counter(li)
li2 = []
pai = []

mxk1=0
mxv1=0
mxk2=0
mxv2=0
for k,v in col.items():
  if (v>1):
    if (k>mxk1):
      mxk2=mxk1
      mxv2=mxv1
      mxk1=k
      mxv1=v
    elif (k>mxk2):
      mxk2=k
      mxv2=v
#print (mxk1,mxv1,mxk2,mxv2)
if (mxv1>3):
	print (mxk1*mxk1)
elif (mxv1>1 and mxv2>1):
  	print(mxk1*mxk2)
else:
	print(0)

   

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

int main() {
  int n;
  cin >> n;
  n*=2;
  int a[n];
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a,a+n,greater<int>());
  int ans=0;
  for(int i=1; i<n; i+=2) ans+=a[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define endl "\n"
const int N=5+1e5;
using namespace std;
int a[N][3],mem[N][3],n;
int  solve(int idx,int t)
{
    int &ret=mem[idx][t];
    if(ret!=-1)
        return ret;
    if(idx>=n)
        return ret=0;
    if(t==0)
        return ret=max(solve(idx+1,1)+a[idx][1],solve(idx+1,2)+a[idx][2]);
    else if(t==1)
        return ret=max(solve(idx+1,0)+a[idx][0],solve(idx+1,2)+a[idx][2]);
    else
        return ret=max(solve(idx+1,0)+a[idx][0],solve(idx+1,1)+a[idx][1]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for(int j=0; j<n; ++j)
        for(int i=0; i<3; ++i)
            cin>>a[j][i];
    memset(mem,-1,sizeof mem);
    cout<<max(max(solve(0,1),solve(0,2)),solve(0,0));
}


Measured memory_bytes: 7296
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int):
    ret = 1
    for i in range(2, N + 1):
        ret *= i
        ret %= MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>

//#include<bits/stdc++.h>


using namespace std;

int t[100005];
int main() {
	
	int n, c, k;
	cin >> n >> c >> k;
	vector<int>p;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		p.push_back(x);
	}
	sort(p.begin(), p.end());

	int ans = 0;
	int y = 0;
	for (int i = 0; i < n; i++) {

		if (i == 0)y++;
		else {
			if (p[i - y] + k >= p[i]) {
				y++;
			}
			else {
				ans++; y = 1;
			}
		}
		if (y == c) {
			ans++; y = 0;
		}
		//cout << y << " " << ans << endl;
	}
	if (y)ans++;


	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 892
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  std::string S;
  std::cin >> S;
  vector<pair<char, int>> v;
  int sum = 1;
  for (int i = 0; i < S.size() - 1; ++i)
  {
    if (S[i] == S[i + 1])
      sum++;
    else
    {
      v.emplace_back(S[i], sum);
      sum = 1;
    }
  }
  v.emplace_back(S[S.size() - 1], sum);
  for (int i = 0; i < v.size(); i += 2)
  {
    for (int j = 0; j < v[i].second - 1; ++j)
    {
      cout << 0 << ' ';
    }
    cout << v[i].second / 2 + v[i].second % 2 + v[i + 1].second / 2 << ' ' << v[i + 1].second / 2 + v[i + 1].second % 2 + v[i].second / 2;
    for (int j = 0; j < v[i + 1].second - 1; ++j)
      cout << ' ' << 0;
    if (i == v.size() - 2)
      cout << endl;
    else
      cout << ' ';
  }

  return 0;
}


Measured memory_bytes: 1528
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import Data.List

getInts :: IO [Int]
getInts = map read . words <$> getLine

createTree :: Int -> Array Int Bool -> [((Int, Int), Int)] -> Array Int [(Int, Int)]
createTree n nl es = runSTArray $ do
    g <- newArray (0, n) [] :: ST s (STArray s Int [(Int, Int)])
    forM_ es $ \((i, j), w) -> when (nl!i && nl!j) $ do
      readArray g i >>= writeArray g i . ((j, w):)
      readArray g j >>= writeArray g j . ((i, w):)
    writeArray g 0 $ map (fmap (const 0)) $ filter snd $ assocs nl
    return g

treeEdges :: Int -> Array Int Bool -> [Int] -> [Int] -> [((Int, Int), Int)]
treeEdges n nl ps ds = filter (\((i, j), _) -> nl!i && nl!j) $ zip (zip [2..] ps) ds

notLeaf :: Int -> [Int] -> Array Int Bool    
notLeaf n ps = runSTArray $ do
    a <- newListArray (1, n) (0:[1,1..]) :: ST s (STArray s Int Int)
    forM_ ps $ \i -> readArray a i >>= writeArray a i . (+1)
    mapArray (>=2) a 

dfs g x p = maximum (0: [w + dfs g y x | (y, w) <- g!x, y /= p])

calc :: Int -> [Int] -> [Int] -> Int
calc n ps ds = sum ds + 2 * sum (map snd te) - dfs tree 0 0
  where
    nl = notLeaf n ps
    tree = createTree n nl te
    te = treeEdges n nl ps ds

main = readLn >>= \n -> when (n/=0) $ calc n <$> getInts <*> getInts >>= print >> main


Measured memory_bytes: 5668
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef long long ll;
ll comp(const void *a,const void *b)
{
  return *(ll *)b-*(ll *)a;
}
int main(void)
{
  int n,m;
  scanf("%d%d",&n,&m);
  printf("%d",(n+m)*(n+m-1)/2-n*m);
  return 0;
}

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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

ll f(string s) {
    int N = s.length();
    ll d = 0, dm = 0, dmc = 0;
    for (char c: s) {
        if (c == 'D') d++;
        if (c == 'M') dm += d;
        if (c == 'C') dmc += dm;
    }
    return dmc;
}

int main() {
	int N; cin >> N;
    string s; cin >> s;
    ll dmc = f(s);
    vector<int> m(N + 1);
    rep(i, N) m[i + 1] = m[i] + (s[i] == 'M');
    int Q; cin >> Q;
    while (Q--) {
        int k; cin >> k;
        k++;
        int d_num = 0;
        ll m_sum = 0;
        ll ans = 0;
        rep(r, N) {
            int l = r - k + 1;
            if (l >= 0 && s[l] == 'D') {
                d_num++;
                m_sum += m[r] - m[l + 1];
            }
            if (s[r] == 'M') m_sum += d_num;
            if (s[r] == 'C') ans += m_sum;
        }
        cout << dmc - ans << endl;
    }
}


Measured memory_bytes: 5296
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		int X = stdIn.nextInt();
		int T = stdIn.nextInt();
		System.out.println((N / X + Math.min(1, N % X)) * T);
	}
}

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

int main(){
  int n,m;
  vector<int> a;
  cin >> n >> m;
  long long sum = 0;
  for(int i = 0; i < m; i++){
    int b;
    cin >> b;
    sum += b;
    if( sum > n ) break;
  }
  cout << ( sum > n ? -1 : n - sum ) << endl;
}


Measured memory_bytes: 3556
#include <set>
#include <map>
#include <unordered_map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double EPS = 1e-9;
const double INF = 2147483647;
#define rep(i, n) rep3(i, 0, n)
#define rep2(i, n) rep3(i, 1, n+1)
#define rep3(i, x, n) for(ll i = x; i < (ll)(n); i++)

template<class T>
void printv(vector<T> v) {
    for(auto it = v.begin(); it != v.end(); it++){
        cout << *it << ",";
    }
    cout << endl;
}
template<class T>
void printp(vector<pair<T,T>> v) {
    for(auto it = v.begin(); it != v.end(); it++){
        cout << (*it).first << "," << (*it).second << endl;
    }
    cout << endl;
}
template<class T>
void printp(map<T,T> v) {
    for(auto it = v.begin(); it != v.end(); it++){
        cout << (*it).first << "," << (*it).second << endl;
    }
    cout << endl;
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数
 
        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
 
        // その結果を push
        res.push_back({a, ex});
    }
 
    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(void){
    ll x,y,z;
    cin >>x>>y>>z;
    cout << (x-z) / (y+z) << endl;
    
    return 0;
}


Measured memory_bytes: 3632