akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

template<typename T>
T pow(T a, long long n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}

template<int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) { if ((x = x_ % mod + mod) >= mod) x -= mod; }
    ModInt& operator+=(ModInt rhs) { if ((x += rhs.x) >= mod) x -= mod; return *this; }
    ModInt& operator-=(ModInt rhs) { if ((x -= rhs.x) < 0) x += mod; return *this; }
    ModInt& operator*=(ModInt rhs) { x = (unsigned long long) x * rhs.x % mod; return *this; }
    ModInt& operator/=(ModInt rhs) { x = (unsigned long long) x * rhs.inv().x % mod; return *this; }

    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }

    friend ostream& operator<<(ostream& s, ModInt<mod> a) { s << a.x; return s; }
    friend istream& operator>>(istream& s, ModInt<mod>& a) { s >> a.x; return s; }
};

using mint = ModInt<1000000007>;

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

    int n, k;
    cin >> n >> k;

    vector<int> div;
    for (int i = 1; i * i <= n; i++) {
        div.push_back(i);
        if (i != n / i) div.push_back(n / i);
    }
    sort(div.begin(), div.end());
    int m = div.size();
    vector<vector<mint>> dp(k, vector<mint>(m));
    dp[0][0] = 1;
    for (int i = 1; i < m; i++) {
        dp[0][i] = div[i] - div[i - 1];
    }

    for (int i = 1; i < k; i++) {
        vector<mint> sum(m);
        for (int j = 0; j < m; j++) sum[j] = dp[i - 1][j];
        for (int j = 1; j < m; j++) sum[j] += sum[j - 1];
        for (int j = 0; j < m; j++) {
            dp[i][j] = sum[m - 1 - j] * (j ? div[j] - div[j - 1] : 1);
        }
    }
    mint ans = 0;
    for (int i = 0; i < m; i++) {
        ans += dp.back()[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 25724
#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 a,b;

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

	in >> a>>b;

	if (a + b == 15) {
		out << "+" << endl;
	}
	else if (a * b == 15) {
		out << "*" << endl;
	}
	else {
		out << "x" << endl;
	}

	return 0;
}
#endif


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

int main() {
  string S;
  cin >> S ;
 
 if(S == "SUN" ){
  cout << 7 << endl;
}else  if(S == "MON" ){
  cout << 6 << endl;
}else if(S == "TUE" ){
  cout << 5 << endl;
} else if(S == "WED" ){
  cout << 4 << endl;
} else if(S == "THU" ){
  cout << 3 << endl;
} else if(S == "FRI" ){
  cout << 2 << endl;
} else if(S == "SAT" ){
  cout << 1 << endl;
}
}


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

ll d[MAX];

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

  char a;
  cin >> a;

  if (isupper(a)) cout << 'A' << '\n';
  else cout << 'a' << '\n';

  return (0);
}


Measured memory_bytes: 3612
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=9e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,a[20]={},x[40000]={};
  cin >> n;
  vector<int> v;
  for(int i=0; i<n; i++) {
    cin >> a[i];
  }
  for(int i=1; i<(1<<n); i++) {
    int cnt=0;
    for(int j=0; j<n; j++) {
      if(i&(1<<j)) {
        cnt+=a[j];
      }
    }
    x[cnt]=1;
  }
  int q;
  cin >> q;
  while(q--) {
    int m;
    cin >> m;
    cout << (x[m]?"yes":"no") << endl;
  }
}


Measured memory_bytes: 3364
#include<stdio.h>


char moji[]={'a','b','c','d','e','f','g','h','i','j'};
char ans[11]={};
int n;

void f(int index,int largest){
  if(index==n){
    puts(ans);
    return;}
  for(int i=0;i<=largest;i++){
    ans[index]=moji[i];
    if(i==largest) f(index+1,largest+1);
    else f(index+1,largest);}
}

int main(){
  scanf("%d",&n);
  f(0,0);
      
  return 0;
}


Measured memory_bytes: 1408
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int x;
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(i&1){
			if(x&1) cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

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

typedef long long ll;
const int N = 5054, M = 254;

int n, m;
ll d[N], ans[N][N];
int v[M][N], l[N], r[N];
int stack[N];

inline void up(ll &x, const ll y) {x < y ? x = y : 0;}
inline void square_add(int r1, int c1, int r2, int c2, int v) {ans[r1][c1] += v, ans[r1][++c2] -= v, ans[++r2][c1] -= v, ans[r2][c2] += v;}

void solve(int *a) {
	int i, top = 0;
	for (i = 1; i <= n; ++i) {
		for (; top && a[i] > a[ stack[top - 1] ]; --top) r[ stack[top - 1] ] = i;
		l[i] = (top ? stack[top - 1] : 0), stack[top++] = i;
	}
	for (; top; r[ stack[--top] ] = n + 1);
	for (i = 1; i <= n; ++i) square_add(l[i] + 1, i, i, r[i] - 1, a[i]);
}

int main() {
	int i, j; ll R = 0;
	scanf("%d%d", &n, &m);
	for (i = 2; i <= n; ++i) scanf("%lld", d + i), d[i] += d[i - 1];
	for (i = 1; i <= n; ++i)
		for (j = 0; j < m; ++j) scanf("%d", v[j] + i);
	for (i = 0; i < m; ++i) solve(v[i]);
	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) ans[i][j] += ans[i][j - 1];
	for (i = 1; i <= n; ++i) for (j = 1; j <= n; ++j) ans[i][j] += ans[i - 1][j];
	for (i = 1; i <= n; ++i) for (j = i; j <= n; ++j) up(R, ans[i][j] - (d[j] - d[i]));
	printf("%lld\n", R);
	return 0;
}

Measured memory_bytes: 203008
#include<bits/stdc++.h>
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }

using Lint=long long;

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

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

    const int MAX=2000;
    vector<bool> ok(MAX+1);

    for(int S=0;S<(1<<N);S++){
        int sum=0;
        for(int i=0;i<N;i++) if(S>>i&1) sum+=a[i];
        if(sum<=MAX) ok[sum]=true;
    }

    int Q; cin>>Q;
    while(Q--){
        int m; cin>>m;
        cout<<(ok[m]? "yes":"no")<<endl;
    }
    return 0;
}


Measured memory_bytes: 3176
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n,a,b;
  string s;
  cin >> n>>a>>b>>s;

  int cnt=0;
  int bcnt=0;
  rep(i,n){
    if(s[i]=='a' && cnt<a+b) {
      cout << "Yes" << endl;
      cnt++;
    }
    else if(s[i]=='b' && bcnt<b && cnt<a+b) {
      cout << "Yes" << endl;
      cnt++;
    }
    else cout << "No" << endl;
    if(s[i]=='b')bcnt++;
  }
  
}


Measured memory_bytes: 896
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e2 + 5;
typedef long long ll;
 int main(){
 	 int n, ans = 0,a[maxn];
 	 scanf("%d",&n);
 	 for ( int i = 1; i <= n; i++) scanf("%d",&a[i]);
 	 sort( a + 1 , a + 1 + n);
 	 for( int i = 1; i <= n; i++){
	 	 if ( a[i] == a[i+1]) continue;
	 	 else ans++;
	 }
	 printf("%d\n",ans);
	 return 0;
 }

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int MOD=1000000007;
using namespace std;
int main(){
    int n;
    cin>>n;
    
    int ans=10000000;
    
    rep(i,0,n-1){
        int tmp=0;
        
        string a=to_string(i+1);
        string b=to_string(n-i-1);
        rep(j,0,a.size()) tmp+=(int)a.at(j)-'0';
        rep(j,0,b.size()) tmp+=(int)b.at(j)-'0';
        
        ans=min(ans,tmp);
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
ans=0
def wari(x):
  an=x
  b=0
  while an<K:
    an=an*2
    b=b+1
  return b

for i in range(N):
  a=i+1
  b=wari(a)
  ans=ans+(0.5)**b
  
print(ans/N)

Measured memory_bytes: 3060
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define PI 3.1415926535
int main(){
cin.tie(0);
int a,b,h,m;
double a_angle,b_angle;
cin >>a >>b >>h>>m;
b_angle=m*6;
a_angle=(h*30+m*0.5);
long double result;
result=sqrt(pow(a*1.0,2)+pow(b*1.0,2)-2*a*b*cos(abs(b_angle-a_angle)*PI/180));

cout<<fixed << setprecision(15)<<result;


return 0;
}


Measured memory_bytes: 4140
MOD = 10 ** 9 + 7

x, y = gets.chomp.split.map(&:to_i)
if (2 * x - y) % 3 != 0 || (2 * y - x) % 3 != 0
  puts "0"
elsif 2 * x < y || 2 * y < x
  puts "0"
else
  h = (2 * x - y) / 3
  w = (2 * y - x) / 3
  m = 10 ** 6 - 1

  inv = Array.new(m + 1)
  m.times do |i|
    if i == 0
      inv[i + 1] = 1
    else
      inv[i + 1] = (- inv[MOD % (i + 1)] * (MOD / (i + 1))) % MOD
    end
  end
  
  r = [h, w].min
  comb = Array.new(r + 1)
  comb[0] = 1

  r.times do |i|
    comb[i + 1] = comb[i] * (h + w - i) * inv[i + 1] % MOD
  end

  puts comb[r]
end

Measured memory_bytes: 24668
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    N,M=MI()
    edge = [[0]*N for _ in range(N)]
    for _ in range(M):
        a,b = MI_()
        edge[a][b] = 1
        edge[b][a] = 1
    
    ans = 0
    for it in permutations([i for i in range(N)]):
        l  =  [i for i in it]
        ok = True
        if l[0]!=0:
            continue
        for i in range(N-1):
            if not edge[l[i]][l[i+1]]:
                ok = False
        ans += ok
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 66792
a, b, c = gets.split.map(&:to_i)

if [a, b, c].select{|n| n % 2 == 0 } != []
  puts 0
  return
end

n = a
m = b

if a >= b && a > c
  n = c
elsif b > c
  m = c
end

puts m * n


Measured memory_bytes: 14324
def main_v2():
    while True:
        n, x = map(int, input().split())
        count = 0
        if n == 0 and x == 0:
            break
        for i in range(1, n-1):
            for j in range(i+1, n):
                k = x - (i + j)
                if k > j and k <= n:
                    count += 1
        print(count)
    return 0


if __name__ == "__main__":
    main_v2()



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

using namespace std;

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

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

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

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

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

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

	int N, x;
	cin >> N >> x;


	VI A(N);
	REP(i, N){
		cin >> A[i];
	}

	LL ret = 0;
	if(A[0] > x){
		ret += A[0] - x;
		A[0] = x;
	}

	FOR(i, 1, N){
		if(A[i - 1] + A[i] > x){
			ret += A[i] + A[i - 1] - x;
			A[i] = x - A[i - 1];
		}
	}

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main(void){
    long long int n,i,j,ans=0,x;
    cin>>n;
    vector<int> vec(n,0);
    for(i=0;i<n;i++){
        cin>>x;
        if(i-x>=0)ans+=vec[i-x];
        if(i+x<n)vec[i+x]++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4056
import numpy as np
if __name__ == "__main__":
    N = int(input())
    line = input().rstrip().split(' ')
    line = np.array(line).astype("int")
    line = np.sort(line)[::-1]
    a = 0
    b = 0
    #print(line)
    for i in range(len(line)):
        if i % 2 ==0:
            a += line[i]
        else:
            b += line[i]
    print(a-b)

Measured memory_bytes: 12420
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input!{
        n: usize,
        s: chars,
    };
    let mut tmp = s[1..].iter().filter(|&c| c == &'E').count();
    let mut min = tmp;

    for i in 1..n {
        if s[i] == 'E'{
            tmp -= 1;
        }
        if s[i-1] == 'W'{
            tmp += 1;
        }
        if tmp < min {
            min = tmp;
        }
    }
    println!("{}", min);
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;

int N;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  vector<pair<pair<long long, long long>, long long> > v(N);
  long long mx_h = 0;
  for(int i=0; i<N; ++i){
    cin >> v[i].first.first >> v[i].first.second >> v[i].second;
    mx_h = max(mx_h, v[i].second);
  }
  for(int i=0; i<=100; ++i){
    for(int j=0; j<=100; ++j){
      vector<long long> HH;
      for(int k=0; k<N; ++k){
         HH.push_back(abs(i - v[k].first.first) + abs(j - v[k].first.second) + v[k].second);
      }
      for(const auto &it: HH){
        int c = 0;
        for(int k=0; k<N; ++k){
          int dist = abs(i-v[k].first.first) + abs(j-v[k].first.second);
          if(max(it-dist, 0ll) == v[k].second)
            ++c;
        }
        if(c == N){
          cout << i << " " << j << " " << it << "\n";
          return 0;
        }
      }
    }
  }
  return 0;
}


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

using namespace std;
 
int a[200];
bool b[200];
 
int main() {
	int x, n;
	cin >> x >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]] = true;
	}
	for (int i = 0; i <= x; i++) {
		if (b[x - i] == false) {
			cout << x - i;
			return 0;
		}
		if (b[x + i] == false) {
			cout << x + i;
			return 0;
		}
	}
	
}


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

int main() {
  int N, K, x;
  cin >> N >> K;

  x = 1;
  for(int i = 0; i < N; i++){
    if(x < K){
      x *= 2;
    }
    else{
      x += K;
    }
  }
  
  cout << x << endl;
}


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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<double> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("b.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	for (auto &i : a) cin >> i;

	if (k >= n)
	{
		cout << "0\n";
		return 0;
	}

	sort(a.begin(), a.end());
	while (k--) a.pop_back();
	cout << accumulate(a.begin(), a.end(), 0LL) << "\n";

	return 0;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		if(b%a==0) {
			pl((a+b));
		}
		else {
			pl((b-a));
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}


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

cnt = 0
for i in A:
    if i < 0:
        cnt += 1
    cnt %= 2
L = [abs(i) for i in A]
if cnt == 0:
    print(sum(L))
else:
    print(sum(L)-2*min(L))

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

using namespace std;

const int INF = 1000000009;

int main() {
  int n;
  cin >> n;

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

  // dp[i] := LISの長さがi+1となるときの末尾要素の最小値
  vector<int> dp(n + 1, INF);
  for (int i = 0; i < n; i++) {
    *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
  }
  int LIS = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
  cout << LIS << endl;

  return 0;
}


Measured memory_bytes: 3628
x,y=gets.split.map &:to_i
l,q,r=$<.map{|s|[9e9,*s.split.map(&:to_i).sort]}
z=s=(l[-x,x]+q[-y,y]).inject:+
(x+y).times{r[1]&&z=[z,s-=(l[-x]<q[-y]?l[~x-=1]:q[~y-=1])-r.pop].max}
p z

Measured memory_bytes: 34060
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
  ll n, a, b, c, d, e;
  cin >> n >> a >> b >> c >> d >> e;

  ll p = min(a, b);
  p = min(p, c);
  p = min(p, d);
  p = min(p, e);

  ll ans = (n + p - 1) / p + 4;

  cout << ans << endl;
}


Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <complex>
#include <ctime>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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; }

using Graph = vector<vector<ll>>;

#define ketasitei setprecision(15) //15桁表示

const ll MOD = 1000000007;
const double PI = 3.1415926535897932;



int main(void)

{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << ketasitei;

	ll n;
	cin >> n;
	vector<double> x(n), y(n);
	rep(i, n)
	{
		cin >> x[i] >> y[i];
	}

	vector<ll> h(n);
	rep(i, n)
		h[i] = i;

	double sum = 0;
	do
	{
		rep(i, n - 1)
		{
			sum += sqrt(pow(x[h[i]] - x[h[i+1]], 2) + pow(y[h[i]] - y[h[i+1]], 2));
		}
	} while (next_permutation(h.begin(),h.end()));

    ll fac=1;
    for(int i=1;i<=n;i++)
        fac*=i;
	cout << sum / (double)fac << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include<iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<deque>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

vector<vector<int> > v(111111);
ll ans,n;
ll ret = 1000000;

bool dfs(int now,int prev)
{
	if(v[now].size() == 1 && prev != -1)
	{
		return false;
	}
	
	int tmp = 0;
	REP(i,v[now].size())
	{
		if(v[now][i] == prev)continue;
		
		if(dfs(v[now][i],now))
		{
			tmp++;
		}
	}
	
	//cout << now << ' ' << v[now].size() - 1 << ' ' << tmp << endl;
	if((int)v[now].size() - 2 > tmp)
	{
		//cout << ' ' << v[now].size()-2-tmp << endl;;
		ans+=v[now].size()-2-tmp;
		tmp++;
	}
	
	if(tmp)	return true;
	else return false;
}

int main()
{
	cin >> n;
	
	REP(i,n-1)
	{
		int a,b;cin >> a >> b;
		v[a].PB(b);
		v[b].PB(a);
	}
	
	REP(i,min(10LL,n))
	{
	//	cout << i << endl;
		ans = 0;
		dfs(i,-1);
		ret = min(ret,ans);
	//	cout << ret << endl;
	}
	
	cout << ret+1 << endl;
	
	return 0;
}

Measured memory_bytes: 10624
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		long N = sc.nextLong();
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		long D = sc.nextLong();
		long E = sc.nextLong();

		long[] h = {A,B,C,D,E};

		long min=Long.MAX_VALUE;

		for(int i=0;i<5;i++)
			min=Math.min(min,h[i]);

		System.out.println((long)Math.ceil((double)N/min)+4);

	}
	//以下、自作ライブラリ

	//最大公約数
	public static long gcd(long a, long b) {
		if (a < b)
			return gcd(b, a);
		long c = 0;
		c = a % b;
		if (c == 0)
			return b;
		return gcd(b, c);
	}

	//最小公倍数
	public static long lcm(long m, long n) {
		return m * n / gcd(m, n);
	}

	//素数判定
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		if (n == 2)
			return true;
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}
}

//以下、高速スキャナークラス
class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 22484
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<iostream>

using namespace std;
string s1,s2;
int N;
int main(){
	cin>>N;
	cin>>s1;
	cin>>s2;
	for (int i=0;i<N;i++){
		bool flag=true;
		for(int j=0;j<N-i;j++){
			if (s1[i+j]!=s2[j]){
				flag=false;
				break;
			}
		}
		if (flag){
			printf("%d\n",N+i);
			return 0;
		}
	}
	printf("%d\n",2*N);

	return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	vector<int> v(n);
	int zero = 0;
	int neg = 0;
	for (auto& x : v)
	{
		cin >> x;
		if (x < 0) neg ^= 1;
		x = abs(x);
	}
	sort(v.begin(), v.end());
	if (neg) v[0] = -v[0];
	LL ans = 0;
	for (auto& x : v) ans += x;
	cout << ans << endl;
	return 0;
}

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

int main(){

    size_t n, p;
    std::cin >> n >> p;

    size_t odd = 0, even = 0;
    for(size_t i = 0; i < n; i++){
        size_t tmp;
        std::cin >> tmp;
        if(tmp % 2 == 1){
            odd++;
        }else{
            even++;
        }
    }

    if(odd == 0 && p == 1){
        std::cout << 0 << std::endl;
    }else if(odd == 0 && p == 0){
        std::cout << (1ul << even) << std::endl;
    }else{
        std::cout << (1ul << (odd - 1)) * (1ul << even) << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
#include<string>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pi acos(-1.0)

#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld\n",a)

#define stll(a) stoll(a,nullptr,10)
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define EL printf("\n")
#define ff first
#define ss second

#define mem(ar,val) memset(ar,val,sizeof(ar))
#define ssort(ar) sort(ar.begin(),ar.end())
#define csort(ar,comp) sort(ar.begin(),ar.end(),comp)

#define bug1(a) cout<<"test "<<a<<endl;
#define bug2(a,b) cout<<"test "<<a<<" "<<b<<endl;
#define bug3(a,b,c) cout<<"test "<<a<<" "<<b<<" "<<c<<endl;
#define bug4(a,b,c,d) cout<<"test "<<a<<" "<<b<<" "<<c<<" "<<d<<endl;

#define fout freopen("output.txt","w",stdout)
#define fin  freopen("input.txt","r",stdin)

/*
auto T=clock();
cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
*/

typedef long long ll;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

int main()
{
    string st;
    ll n;
    cin>>st;
    n= st.length();
    for(int i=0;i<n;i++)
    {
        if(st[i]=='?')st[i]='D';
    }

    cout<<st<<endl;

}








Measured memory_bytes: 3752
BEST = 22

def bmi(h, w)
  return w / (h * 0.01) ** 2
end

until (n = gets.to_i).zero?
  tmp1, best = Float::INFINITY, nil
  
  n.times do
    i, h, w = gets.split.map(&:to_i)
    tmp2 = (BEST - bmi(h, w)).abs
    
    if tmp2 < tmp1
      best = i
      tmp1 = tmp2
    end
  end
  
  puts best
end

Measured memory_bytes: 6140
#include <bits/stdc++.h>
using namespace std;
typedef long long     ll;
const ll big=2e6+5;

#define endl "\n";
ll a[106];
int main()
{ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll x,y,a,b;
    cin>>x>>y;
    for(a=0;a<=x;a++){
        b=abs(x-a);
        ll k=a*2+b*4;
        if(k==y){cout<<"Yes\n";return 0;}
    }
    cout<<"No\n";


    return 0;
}

Measured memory_bytes: 3688
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        int countZero = 0;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
            if (a[i] == 0) {
                countZero++;
            }
        }
        sc.close();

        // 主処理
        Set<Integer> set = new HashSet<>(Arrays.asList(a));
        boolean judge;
        if (countZero == n) {
            judge = true;
        } else if (n % 3 == 0 && countZero == n / 3 && set.size() == 2) {
            judge = true;
        } else if (n % 3 == 0 && set.size() == 3) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : set) {
                map.put(num, 0);
            }
            for (int i = 0; i < n; i++) {
                map.put(a[i], map.get(a[i]) + 1);
            }
            Set<Integer> valueSet = new HashSet<>();
            int xorSum = 0;
            for (int key : map.keySet()) {
                valueSet.add(map.get(key));
                xorSum = xorSum(xorSum, key);
            }
            judge = valueSet.size() == 1 && xorSum == 0;
        } else {
            judge = false;
        }
        String result = judge ? "Yes" : "No";

        // 出力
        System.out.println(result);
    }

    public static int xorSum(int a, int b) {
        String bina = new StringBuilder(Integer.toBinaryString(a)).reverse().toString();
        String binb = new StringBuilder(Integer.toBinaryString(b)).reverse().toString();
        int minlen = Math.min(bina.length(), binb.length());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < minlen; i++) {
            if (bina.charAt(i) == binb.charAt(i)) {
                sb.append("0");
            } else {
                sb.append("1");
            }
        }
        if (bina.length() < binb.length()) {
            sb.append(binb.substring(minlen));
        } else if (binb.length() < bina.length()) {
            sb.append(bina.substring(minlen));
        }
        return Integer.parseInt(sb.reverse().toString(), 2);
    }
}


Measured memory_bytes: 60996
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)
const long double PI = (acos(-1));


int main() {

	string s;
	cin >> s;

	int ans = 0;
	if (s[0] == '1') ans = 1;
	if (s[0] == '2' && s[1] == '0') {
		if (s[2] <= '1' && s[2] <= '9') {
			if (s[5] == '0' && s[6] <= '4') {
					ans = 1;
			}
		}
	}

	if (ans == 0) cout << "TBD" << endl;
	else cout << "Heisei" << endl;

	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int main(void){
    
    int N;
    cin >> N;
    
    if(N >= 1 && N <= 9){
        cout << "Yes" << endl;
        return 0;
    }
    
    for(int i = 2; i <= 9; i++){
        if(N % i == 0 && N / i <= 9){
            cout << "Yes" << endl;
            return 0;
        }
    }
    
    cout << "No" << endl;
    
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vpll vector < pair<long long,long long> >
#define fill(a,val)  memset(a,val, sizeof (a))
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(cont) cont.begin(), cont.end()
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(max(a,d),max(b,c))
#define MAX   1e9
#define MIN  -1e9
typedef map<int,int> mpi;
typedef set<int> seti;
typedef multiset<int> mseti;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i, n)    for(long long int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(long long int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(long long int i = a; i >= (n); --i)
#define repn(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define trav(a, x) for(auto& a : x)
#define dbg(x) cout << #x << " = " << x << '\n'
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl
#define inp(a,start,len) for(long long int i = start;i < len;i++) cin>>a[i]
struct Interval{ll start,end;};
bool compare(Interval i1, Interval i2) {return (i1.start < i2.start);}


int main(){
	fio;
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	ll T = 1;
	// cin>>T;
	while(T--){
		ll H,W,M;
		cin>>H>>W>>M;
		map< pll, ll > m;
		ll countv[W+1],counth[H+1];
		fill(counth,0);
		fill(countv,0);
		rep(i,M){
			ll h,w;
			cin>>h>>w;
			m[mp(h,w)] = 1;
			countv[w]++;
			counth[h]++;
		}
		ll maxh = 0,maxv = 0;
		repA(i,1,H){
			if(counth[i]>maxh){
				maxh = counth[i];
			}
		}
		repA(i,1,W){
			if(countv[i]>maxv){
				maxv = countv[i];
			}
		}
		vll vh,vv;
		repA(i,1,H){
			if(maxh == counth[i])
				vh.pb(i);
		}
		repA(i,1,W){
			if(maxv == countv[i])
				vv.pb(i);
		}
		ll sub = 1;
		rep(i,vh.size()){
			rep(j,vv.size()){
				if(!(m[mp(vh[i],vv[j])])){
					sub = 0;
					break;
				}
			}
		}
		cout<<(maxh+maxv-sub);
	}
	return 0;
}


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

int m;
long nDigit = 0, sumDigit = 0; 

int main() {
    cin >> m;
    for (int i = 0; i < m; i++){
        long d, c;
        cin >> d >> c;
        nDigit += c;
        sumDigit += d*c;
    }
    
    cout << nDigit - 1 + (sumDigit - 1) / 9 << endl;

    return 0;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
ll INF = (1LL << 31) - 1;
int MOD = 1e9+7;
ll N,A,B;
vector<ll> V;
bool judge(ll k){
    ll cnt = 0;
    rep(i,0,N){
        if(V[i] > B * k){
            cnt += (V[i] - B * k + A - 1) / A;
        }
    }
    return cnt <= k;
}
main(){
    cin >> N >> A >> B;
    A -= B;
    V.resize(N);
    rep(i,0,N)cin >> V[i];
    ll ok = INF, ng = 0;
    while(ok - ng > 1){
        ll mid = (ok + ng) / 2;
        if(judge(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 1024
import Control.Applicative
import Control.Monad
import Data.Vector.Unboxed.Mutable (IOVector, STVector)
import qualified Data.Vector.Unboxed.Mutable as VM

main :: IO ()
main = readLn >>= solve

solve :: Int -> IO ()
solve n = do
  let ls = takeWhile ((< n) .(^2)) [1..]
  v <- VM.replicate (n + 1) 0 :: IO (IOVector Int)
  forM_ ls $ \x -> do
    forM_ ls $ \y -> do
      forM_ ls $ \z -> do
        let m = x * x + y * y + z * z + x * y + y * z + z * x
        when (m <= n) $ do
          VM.modify v (+1) m
  forM_ [1 .. n] $ \i -> do
    c <- VM.read v i
    print c


Measured memory_bytes: 5076
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr int mod = 1e9 + 7;

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

/*-------------------------------------------*/

int n;
ll a[3000], dp[3000][3000];
bool fin[3000][3000];

ll f(int l, int r) {
    if(l > r) return 0;
    if(!fin[l][r]) {
        fin[l][r] = true;
        if(r + l + n & 1)
            dp[l][r] = max(a[l] + f(l + 1, r), f(l, r - 1) + a[r]);
        else
            dp[l][r] = min(f(l + 1, r) - a[l], f(l, r - 1) - a[r]);
    }
    return dp[l][r];
}

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

    cin >> n;
    rep(i, n) cin >> a[i];

    cout << f(0, n - 1) << endl;

    return 0;
}

Measured memory_bytes: 78464
#include<bits/stdc++.h>
using namespace std;
#define PI 3.14159265359
int main(){
    int N; cin>>N;
    int count=0;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    bool flag=1;
    while(flag) {
        flag=0;
        for (int i = N - 1; i > 0; i--) {
            if (v[i - 1] > v[i]) {
                swap(v[i - 1], v[i]);
                count++;
                flag=1;
            }
        }
    }
    for(int i=0;i<N;i++){
        cout<<v[i]<<" \n"[i==N-1];
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3112
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
        String S = sc.next();
        char[]ss = S.toCharArray();
        String T = sc.next();
        char[]t = T.toCharArray();

        int cou = 0;
        for(int i=0; i<S.length(); i++) {
        for(int j=0; j<T.length(); j++) {	 
      	if(ss[i] == t[j]) {
      		if(S.equals (T.substring(j, T.length()) + T.substring(0, j))) {
        			cou++;
        		}
        	}
        }
        }
        if(cou > 0){
            System.out.println("Yes");    
        }else{
            System.out.println("No");
    }
}
}

Measured memory_bytes: 42428
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define maxm 
#define mod 
#define maxn 
 
int main()
{
	int n, x, s = 0, t = 0;
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		if (x & 1) s++;
		else if (x % 4 == 0) t++;
	}	
	if (t >= s) puts("Yes");
	else if (t + 1 == s && t + s == n) puts("Yes");
	else puts("No");
}

Measured memory_bytes: 256
N=int(input())
OKflag=False

# 各個数のケーキについて
for nc in range(N//4+1):
    res=N-(nc*4) # ドーナツで払う金額

    if res%7==0: # 割り切れるなら
        OKflag=True
        break

if OKflag==True: # ある場合
    print("Yes")
else: # ない場合
    print("No")

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

using namespace std;
int main()
{   int n;
    cin >> n;
    vector<int> a;

    for (int i = 0; i < n; i++){
      int a_;
      cin >> a_;
      a.push_back(a_);
    }
    vector<int> b;
    for(int i = n-1; i >= 0; i-=2){
      cout << a[i] << ' ';
    }
    for(int i = n%2; i < n; i+=2){
      cout << a[i];
      if (i+2 < n)cout << ' ' ;
    }
    
    return 0;
}


Measured memory_bytes: 3060
#include <iostream> 
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<queue>
#include<deque>
#include<iomanip>
#include<sstream>
#include<cmath>
#include<tuple>
#include<bitset>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define req(i,n) for(int i = 1;i <=  n; i++)
#define rrep(i,n) for(int i = n -1;i >= 0;i--)
#define ALL(obj) begin(obj), end(obj)
typedef long long int ll;
typedef long double ld;
const ll INF = (1<<60);
int k, x, m, n, h, r, w,y,d = 0; ll sum = 0; string s,t;
const ld PI = acos(-1);
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
    std::fill((T*)array, (T*)(array + N), val);
}
int main() {
    cin >> n; vector<int> a(n+1),b(n+1,0);
    req(i, n) cin >> a[i];
    for (int i = n; i > 0; i--) {
        sum = 0;
        for (int j = i + i; j <= n; j += i) {
            if (b[j]) sum += b[j];
        }
        if (sum % 2 != a[i]) b[i] = 1;
    }
    req(i, n) {
        if (b[i]) d++;
    }cout << d << endl;
    req(i, n) {
        if (b[i]) cout << i << endl;
    }
}

Measured memory_bytes: 2432
import itertools

n = int(input())

s = [0 for _ in range(n)]
in_a = [0 for _ in range(n)]
dic_tmp = {}
dic_ar = [0 for _ in range(n)]
for i in range(n):
    in_a[i] = input()

cnt = 0
for i in range(n):
    s = sorted(in_a[i])
    s = "".join(s)
    if(s in dic_tmp):
        cnt += dic_tmp[s]
        dic_tmp[s] += 1
    else:
        dic_tmp[s] = 1

print(cnt)


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

int main(){
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
   	ll a,b,q;
   	cin >> a >> b >> q;
   	vector <ll> shrine(a);
   	vector <ll> temple(b);
   	for (int z=0;z<a;z++){
   		cin >> shrine[z];
   	}
   	for (int z=0;z<b;z++){
   		cin >> temple[z];
   	}
   	sort(shrine.begin(),shrine.end());
   	sort(temple.begin(),temple.end());
   	for (int z=0;z<q;z++){
   		ll temp;
   		cin >> temp;
   		auto sit = upper_bound(shrine.begin(),shrine.end(),temp);
   		auto tit = upper_bound(temple.begin(),temple.end(),temp);
   		ll answer = LLONG_MAX;
   		if (sit != shrine.end() && tit != temple.end()){
   			answer = min(min(abs(*sit-temp),abs(*tit-temp))+abs(*sit-*tit),answer);
   		}
   		if (sit != shrine.begin() && tit != temple.begin()){
   			answer = min(min(abs(*(sit-1)-temp),abs(*(tit-1)-temp))+abs(*(sit-1)-*(tit-1)),answer);
   		}
   		if (sit != shrine.end() && tit != temple.begin()){
   			answer = min(abs(*sit-*(tit-1))+min(abs(*sit-temp),abs(*(tit-1)-temp)),answer);
   		}
   		if (sit != shrine.begin() && tit != temple.end()){
   			answer = min(abs(*tit-*(sit-1))+min(abs(*tit-temp),abs(*(sit-1)-temp)),answer);
   		}
   		cout << answer << endl;
   	}
   	cin >> a;
}

Measured memory_bytes: 2944
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;

    int data[n];
    for(int i = 0; i < n; i++) {
      cin >> data[i];
    }
    sort(&data[0], &data[n]);

    unsigned int ans = 0;
    for(int i = 0; i < n; i++) {
      ans += data[i] * (n - i - 1);
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 0
MOD = 10**9 + 7
 
N,K = [int(s) for s in input().split()]
 
comb = [[1]]
for i in range(N + 1):
    comb.append([1])
    for j in range(i):
        comb[-1].append((comb[-2][j] + comb[-2][j + 1]) % MOD)
    comb[-1].append(1)
    
def combi(n,k):
  return comb[n][k] if n >= k else 1

for i in range(1,K+1):
  if i <= N-K+1:
    print((combi(N-K+1,i) * combi(K-1,i-1)) % MOD)
  else:
    print(0)

Measured memory_bytes: 83816
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x,cn;
    vector<int>v;
    vector<int>v1;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    cin>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x;
        v1.push_back(x);
    }
    sort(v.begin(),v.end());
    sort(v1.begin(),v1.end());
    if(includes(v.begin(),v.end(),v1.begin(),v1.end()))
    {
        cout<<"1"<<endl;
    }
    else
        cout<<"0"<<endl;
    return 0;
}



Measured memory_bytes: 5088
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        int N;
        double res=0;
        Scanner in=new Scanner(System.in);
        N=in.nextInt();
        double[]p=new double[N+1];
        double[][] dp=new double[N+1][N+1];//前i个中有j个硬币朝上
        for(int i=1;i<=N;i++)p[i]=in.nextDouble();
        dp[0][0]=1;
        for(int i=1;i<=N;i++){
          dp[i][0]=dp[i-1][0]*(1-p[i]);
          for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
          }
        }
        for(int i=N/2+1;i<=N;i++){
          res+=dp[N][i];
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 133740