akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline #文字列入力のときは注意

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.base = [0]* (n+1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.base[i] += x
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
    def get(self, i):
        return self.base[i]

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
     
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
     
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

#    def get(self, s):
#        return self.p.sum(s+1) + self.q.sum(s+1) * (s+1) - \
#               self.p.sum(s) - self.q.sum(s) * s
    def get(self, s):
        return self.p.get(s+1) + self.q.get(s+1) * (s+1) + self.q.sum(s) 



n,m = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(n)]

lr.sort(key=lambda x: x[1]-x[0])

#print(lr)

omiyage = RangeUpdate(m+1)
index = 0
for d in range(1,m+1):
    while(index < n and lr[index][1] - lr[index][0] < d):
        omiyage.add(lr[index][0]+1, lr[index][1]+1, 1)
        index+=1
    ans = 0
    pos = 0
    while(pos <= m):
        ans += omiyage.get(pos+1)
        pos += d
    ans += n-index
    print(ans)
    


Measured memory_bytes: 123220
"use strict";

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim();

const inputs = input.split("\n");

const parse = (val) => val.split(" ").map(i => +i);

const sort = (arr) => arr.sort( (a, b) => b - a );

const transform = (arr) => sort(parse(arr));

const exec = (inputs) => {
  const firstLine = parse(inputs.shift());
  const K = firstLine[3];
  const As = transform(inputs[0]);
  const Bs = transform(inputs[1]);
  const Cs = transform(inputs[2]);

  const res = [];
  for (let a = 0; a < As.length; a++) {
    for (let b = 0; b < Bs.length; b++) {
      for (let c = 0; c < Cs.length; c++) {
        if ((a+1) * (b+1) * (c+1) <= K) {
          res.push(As[a] + Bs[b] + Cs[c]);
        } else {
          break;
        }
      }
    }
  }
  return sort(res).slice(0, K);
}

console.log(exec(inputs).join("\n"));


Measured memory_bytes: 32436
def main():
    a, b, c, x, y = (int(i) for i in input().split())
    ans = a*x + b*y
    ans = min(ans, 2*c*max(x, y))
    if x < y:
        d = y-x
        d *= b
    else:
        d = x-y
        d *= a
    ans = min(ans, 2*c*min(x, y) + d)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

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

    bool flag = 1;
    int cnt = 0;

    int i = 0;
    while(flag) {
        flag = 0;
        for(int j = n-1; j > i; j--) {
            if(A[j] < A[j-1]) {
                int tmp = A[j];
                A[j] = A[j-1];
                A[j-1] = tmp;
                flag = 1;
                cnt++;
            }
        }
        i++;
    }

    // for(int i = 0; i < n; i++) {
        // if(i != n-1) cout << A[i] << ' ';
        // else cout << A[i] << endl;
        // i != n-1 ? cout << A[i] << ' ' : cout << A[i] << endl;
    // }

    for(int i = 0; i < n; i++) i != n-1 ? cout << A[i] << ' ' : cout << A[i] << endl;

    cout << cnt << endl;

    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

template <typename T>
inline void read(T &x)
{
    T data = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        data = (data << 3) + (data << 1) + ch - '0';
        ch = getchar();
    }
    x = f * data;
}

const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1e5 + 9;

signed main()
{
    //freopen("in.txt","r",stdin);
    //freopen("data.txt","w",stdout);
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    //std::cout.tie(0);
    string s;
    cin >> s;
    int len = 0, ans = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        if (s[i] == 'R')
            len++;
        else
            ans = max(ans, len), len = 0;
    }
    ans = max(ans, len);
    cout << ans << '\n';
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Measured memory_bytes: 3596
K, N = map(int,input().split())

A = list(map(int,input().split()))




max_range = (K+A[0]-A[N-1])

for i in range(N-1):
    if max_range < A[(i+1)%K]-A[i%K]:
        max_range = A[i+1]-A[i]
        


if max_range>=K/2:
    print(K-max_range)
else:
    print(K-max_range)


Measured memory_bytes: 25452
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++) 
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int N,C,K;
    cin >> N >> C >> K;
    int now=0;
    int ans=0;
    int fast=0;
    vector<int> T(N);
    rep(i,N)cin >> T[i];
  	sort(all(T));
    rep(i,N){
        if(i==0){
            fast=T[i];
        }
        else if(T[i]>fast+K){
            fast=T[i];
            now=0;
            ans++;
          	cerr << i;
        }
        else if(now==C){
            fast=T[i];
            now=0;
            ans++;
          	cerr << i;
        }
        now++;
    }
    ans++;
    cout << ans;


}

/*



 */



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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/11  Problem: ABC 087 B / Link: http://abc087.contest.atcoder.jp/tasks/abc087_b  ----- */


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

	LL A, B, C, X; cin >> A >> B >> C >> X;
	LL ans = 0LL;
	FOR(i, 0, A + 1) {
		FOR(j, 0, B + 1) {
			FOR(k, 0, C + 1) {
				if (i * 500 + j * 100 + k * 50 == X)ans++;
			}
		}
	}
	
	
	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		int N=sc.nextInt();

		int[] dp=new int[N+1];
		int INF=100001;

		for(int i=0;i<N+1;i++) dp[i]=INF;

		dp[0]=0;

		int n6=6;
		int n9=9;

		double cnt6=2.0;
		double cnt9=2.0;

		for(int i=1;i<N+1;i++) {

			dp[i]=Math.min(dp[i], dp[i-1]+1);

			if(i==Math.pow(6, cnt6)) {
				n6=(int)Math.pow(6, cnt6);
				cnt6++;
			}

			if(i==Math.pow(9, cnt9)) {
				n9=(int)Math.pow(9, cnt9);
				cnt9++;
			}

			if(i>=6)	dp[i]=Math.min(dp[i], dp[i-n6]+1);
			if(i>=9) dp[i]=Math.min(dp[i], dp[i-n9]+1);


			//System.out.println(i+" "+dp[i]);
		}

		System.out.println(dp[N]);

		sc.close();
	}
}


Measured memory_bytes: 23252
L,R=$<.read.split.map(&:to_i)

min = 2020
L.upto([R-1,L+2018].min) do |i|
    (L+1).upto([R,L+1+2018].min) do |j|
        n = (i*j) % 2019
        min = n if n < min
    end
end

puts min

Measured memory_bytes: 1788
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

struct node {
	int from;
	int to;
	int c;
};

vector<node> vec;

int n, m, p, dist[2509], pre[3000];
bool vis[3000], edge[3000][3000], vis2[3000];

void dfs(int x, int p)
{
	vis[x] = true;
	pre[x] = p;
	for (int i = 1; i <= n; i++) {
		if (edge[x][i] && !vis[i])
			dfs(i, x);
	}
}

void dfs2(int x)
{
	vis2[x] = true;
	for (int i = 1; i <= n; i++) {
		if (!vis2[i] && edge[x][i]) {
			dfs2(i);
		}
		if (edge[x][i] && vis[i]) {
			vis[x] = true;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> p;
	vec.resize(m);
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> vec[i].from >> vec[i].to >> tmp;
		edge[vec[i].from][vec[i].to] = true;
		vec[i].c = p - tmp;
	}
	dfs(1, 0);
	memset(vis, 0, sizeof(vis));
	int cur = n;
	while (cur) {
		vis[cur] = true;
		cur = pre[cur];
	}
	dfs2(1);
	for (int i = 2; i <= n; i++)
		dist[i] = 1e9;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[vec[j].from] + vec[j].c < dist[vec[j].to]) {
				dist[vec[j].to] = dist[vec[j].from] + vec[j].c;
				pre[vec[j].to] = vec[j].from;
			}
		}
	}
	for (int j = 0; j < m; j++) {
		if (dist[vec[j].from] + vec[j].c < dist[vec[j].to] && vis[vec[j].from]) {
			cout << -1 << E;
			return 0;
		}
	}
	cout << max(-dist[n], 0) << E;
	//system("pause");
	return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> P;
#define INF 10000000000000
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i < (int)(n); i++)
#define repN_1(i, n) for(int i = 0; i < (int)(n - 1); i++)
#define repM(i, n) for(int i = (int)(n - 1); i >= 0; i--)
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; }

int main()
{
	int a, b;

	cin >> a >> b;
	
	string aa, bb;
	aa = "";
	bb = "";

	rep(i, b)
		aa += to_string(a);

	rep(j, a)
		bb += to_string(b);

	int len = min(aa.length(), bb.length());

	rep(i, len)
	{
		if (aa[i] < bb[i])
		{
			cout << aa << endl;
			return 0;
		}
		else if (aa[i] > bb[i])
		{
			cout << bb << endl;
			return 0;
		}
	}

	if (aa.length() == bb.length())
		cout << aa << endl;
	else if (aa.length() < bb.length())
		cout << aa << endl;
	else
		cout << bb << endl;

	return 0;
}

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


using namespace std;



double probablitythatheadisalwaysgre(double *arr,int n){


   double DP[n+1][n+1]; 
 
  for(int i=1;i<=n;i++){

    DP[0][i]=0;


  }

  for(int i=0;i<=n;i++)
  	DP[i][0]=1;

 
  for(int i=1;i<=n;i++){

  for(int j=1;j<=n;j++){

    
     if(i<j)
     	DP[i][j]=0;
    
    else{


       DP[i][j]=arr[i-1]*DP[i-1][j-1]+(1-arr[i-1])*DP[i-1][j];


    }


  }


  }

int x=n/2+1;

 double ans=0;

for(int i=x;i<=n;i++)
  ans+=DP[n][i];


return DP[n][x];
}

int main(){


  int n;

  cin>>n;

  double arr[n];


  for(int i=0;i<n;i++)
  	cin>>arr[i];

  double res=probablitythatheadisalwaysgre(arr,n);

  cout<<fixed<<setprecision(10)<<res<<endl;


	return 0;
}

Measured memory_bytes: 74096
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty ;; $n:expr) => {
        (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
    };
}

fn main() {
    let s = get!(String).chars().collect::<Vec<_>>();
    let mut r = 0;
    let mut last = 'X';
    for c in s {
        if last != c {
            r += 1;
        }
        last = c;
    }
    println!("{}", r - 1);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    int n;
    cin >> n;
    cout << (n/10%111==0 || n%1000%111==0 ? "Yes":"No") << endl;
}


Measured memory_bytes: 256
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const int LIMIT = 123456789;
const int MAX = 202020;
int d[MAX];   // 頂点 1 からの 距離 を 保存.
int bef[MAX]; // 前回訪問した頂点.

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    d[s] = 0;    // スタート地点は, 距離ゼロを指定.
    bef[s] = -1; // スタート地点は, 前回訪問した頂点が存在しないので, -1 を 指定.
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e), bef[e] = u;
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 初期化.
    rep(i, N) bef[i] = LIMIT;
    
    // 3. 頂点 1 から 各頂点までの距離を計算.
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 4. 訪問不可能な頂点があるかの確認.
    bool ok = true;
    rep(i, N){
        if(bef[i] == LIMIT){
            ok = false;
            break;
        }
    }
    
    // 5. 出力.
    if(ok){
        puts("Yes");
        repx(i, 1, N) printf("%d\n", bef[i] + 1);
    }else{
        puts("No");
    }
    return 0;
    
}

Measured memory_bytes: 10612
using System;


class Program
{
    static void Main(string[] args)
    {
        string[] In = Console.ReadLine().Split(' ');
        int x = int.Parse(In[0]);
        int y = int.Parse(In[1]);
        bool flag = false;
        for(int i=0;i<=25;i++ )//4本
        {
            int j = x - i;//2本
            int sum = 4 * i + 2 * j;
            if (sum == y && j>=0)
            {
                flag = true;
                break;
            }
        }
        if (flag) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}



Measured memory_bytes: 27532
#!/usr/bin/env ruby
n = STDIN.readline().strip.to_i
ts = []
n.times.each {|i| ts << STDIN.readline().split(' ').map(&:to_i)}
def check_next_point(t, x, y, t0, x0, y0)
  xd = (x - x0).abs
  yd = (y - y0).abs
  td = t - t0
  diff = td - (xd + yd)
  return false if diff < 0
  return diff.even?
end
def check(ts)
  t0, x0, y0 = 0, 0, 0
  ts.each do |t|
    return false if not check_next_point(t[0], t[1], t[2], t0, x0, y0)
    t0, x0, y0 = t[0], t[1], t[2]
  end
  true
end
puts "#{check(ts) ? 'Yes' : 'No'}"

Measured memory_bytes: 9596
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 1e5 + 10, MD = 1e9 + 7;
int n, k, a[110];
ll dp[110][MAXN];

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

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

	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		ll ans = 0;
		for (int j = 0; j <= k; ++j) {
			ans += dp[i - 1][j];
			if(j - a[i] - 1 >= 0) ans -= dp[i-1][j - a[i] - 1];
			ans = (ans + MD) % MD;
			dp[i][j] = ans;
		}
	}

	cout << dp[n][k] << '\n';

	return 0;
}


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

typedef long long ll;

ll N, M;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main() {
    cin >> N >> M;
    mint ans = 1;
    combination c((int)1e6);

    ll rest = M;
    for (ll i = 2; i * i <= M; i++) {
        if (rest % i == 0) {
            int cnt = 0;
            while (rest % i == 0) {
                rest /= i;
                cnt++;
            }
            // cout << N - 1 + cnt << " " << cnt << endl;
            ans *= c(N - 1 + cnt, cnt);
            // cout << ans.x << endl;
        }
    }
    // cout << rest << endl;
    if (rest != 1) {
        ans *= c(N - 1 + 1, N - 1);
    }

    cout << ans.x << endl;
}

Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int a,b,c; cin >> a >> b >> c;
    vector<int> cnt(10,0);
    cnt[a-1]++; cnt[b-1]++; cnt[c-1]++;
    if (cnt[5-1] == 2 && cnt[7-1] == 1) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rep2(i,s,t) for(int i = s; i <= t; ++i)
#define rev(i,n) for(int i = n-1; i >= 0; --i)
#define rev1(i,n) for(int i = n; i > 0; --i)
#define rev2(i,s,t) for(int i = s; i >= t; --i)
#define F first
#define S second
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 ll = long long;
using pi = pair<int,int>;
using vi = vector<ll>;
using vii = vector<vi>;
int main()
{
  int n; cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];

  ll inf = (1LL << 60);
  vii dp(n+1, vi(2, -inf));
  dp[0][0] = 0;
  rep1(i,n) {
    chmax(dp[i][0], dp[i-1][0] + a[i-1]);
    chmax(dp[i][1], dp[i-1][0] - a[i-1]);
    chmax(dp[i][0], dp[i-1][1] - a[i-1]);
    chmax(dp[i][1], dp[i-1][1] + a[i-1]);        
  }
  // rep(i,n+1) {
  //   cout << dp[i][0] << ":" << dp[i][1] << "\n";
  // }
  cout << dp[n][0] << "\n";
  return 0;
}


Measured memory_bytes: 9444
from queue import Queue


def distances(tree: list, size: int, root: int)->list:
    dists = [0] * size

    q = Queue()
    q.put((root, -1, 0))

    while not q.empty():
        v, prev, d2v = q.get()
        dists[v] = d2v

        for u, dv2u in tree[v]:
            if u == prev:
                continue
            q.put((u, v, d2v + dv2u))

    return dists


def fennec_vs_snuke(N: int, edges: list)->str:
    tree = [[] for _ in range(N)]
    for a, b in edges:
        tree[a-1].append((b-1, 1))
        tree[b-1].append((a-1, 1))

    d_from1 = distances(tree, N, 0)
    d_fromN = distances(tree, N, N-1)

    fennec, snuke = 0, 0
    for i in range(N):
        if d_fromN[i] < d_from1[i]:
            snuke += 1
        else:
            fennec += 1
    return 'Fennec' if fennec > snuke else 'Snuke'


if __name__ == "__main__":
    N = int(input())
    edges = [tuple(int(s) for s in input().split()) for _ in range(N-1)]
    ans = fennec_vs_snuke(N, edges)
    print(ans)


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct UnionFind {
    vector<int> par, rank, _size;
    UnionFind(int n):par(n), rank(n), _size(n, 1) { for (int i = 0; i < n; ++i) par[i] = i; }
    int find(int x) {
        if (par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] > rank[y]) swap(x, y);
        par[x] = y; _size[y] += _size[x];
        if (rank[x] == rank[y]) rank[y]++;
    }
    int size(int x) { return _size[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
};

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

    vector<int> p(N);
    for (auto &i : p) cin >> i;

    vector<P> v(M);
    for (auto &i : v) cin >> i.first >> i.second;

    UnionFind uf(N+1);
    for (auto &i : v) uf.unite(i.first, i.second);

    int ans = 0;
    rep(i, N) {
        if (uf.same(p[i], i+1)) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 2560
import sys
input=sys.stdin.readline
n=int(input())
a_list=list(map(int,input().split()))
A=sum(a_list)
ha=0
for i in a_list:
    ha+=i
    if ha>=A/2:
        hb=ha-i
        break
ans=min(ha+ha-A,A-2*hb)
print(ans)



Measured memory_bytes: 81104
using System;

namespace ITP1_6_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string number = Console.ReadLine();
            int n = int.Parse(number.Split(' ')[0]);
            int m = int.Parse(number.Split(' ')[1]);
            int[,] A = new int[n, m];
            int[] b = new int[m];
            int[] c = new int[n];

            for (int i = 0; i < n; i++)   //n×mの行列Aの入力
            {
                string number1 = Console.ReadLine();
                for (int j = 0; j < m; j++)
                {
                    A[i, j] = int.Parse(number1.Split(' ')[j]);
                }
            }
            for (int i = 0; i < m; i++)       //m×1の行列bの入力
            {
                string number2 = Console.ReadLine();
                b[i] = int.Parse(number2);
            }
            for (int i = 0; i < n; i++)   //積の計算
            {
                for (int j = 0; j < m; j++)
                {
                    c[i] += A[i, j] * b[j];
                }
            }
            for (int i = 0; i < n; i++)
            {
                Console.WriteLine("{0}", c[i]);
            }
        }
    }
}


Measured memory_bytes: 22032
n,a=map(int,input().split())
x=list(map(int,input().split()))

for i in range(n):
    x[i]-=a
    
dp=[0]*(2*n*50+2)
dp[0]=1
for i in range(n):
    h=dp[:]
    for j in range(-(n-1)*50,(n-1)*50+1):
        h[j]+=dp[j-x[i]]
    dp=h
print(dp[0]-1)

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

using namespace std;

int main() {
//        freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
        int n, m;
        scanf("%d%d", &n, &m);
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
                scanf("%lld", &a[i]);
        }
        sort(a.begin(), a.end());
        vector<pair<long long, int>> pairs;
        for (int i = 0; i < m; i++) {
                int x;
                long long y;
                scanf("%d%lld", &x, &y);
                pairs.push_back({y, x});
        }
        sort(pairs.begin(), pairs.end());
        int cur = m - 1;
        for (int i = 0; i < n; i++) {
                if (pairs[cur].first > a[i]) {
                        pairs[cur].second--;
                        a[i] = pairs[cur].first;
                        if (pairs[cur].second == 0) {
                                if (cur == 0) {
                                        break;
                                } else {
                                        cur--;
                                }
                        }
                }
        }
        long long tot = 0;
        for (auto x : a) {
                tot += x;
        }
        printf("%lld\n", tot);
        return 0;
}


Measured memory_bytes: 3188
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    string c;
    int am, pm;
    while (cin >> c) {
        scanf("%d%d",&am,&pm);
        int resp = am + pm;
        int price = am * 200 + pm * 300;
        cout << c;
        printf(" %d %d\n", resp, price);
    }
}

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

int main(){
  int x,y;
  cin >> x>>y;
  int A=0,B=0;
  if(x==(-y)){
    cout<<1<<endl;
    return 0;
  }
  if(((x>0)&&(y>0))&&(x<y)){
    cout<<y-x<<endl;
    return 0;
  }
  if(((x>0)&&(y>0))&&(x>y)){
    cout<<abs(y-x)+2<<endl;
    return 0;
  }  
  
  if((x<0)&&(y>0)){
    cout<<abs(y-abs(x))+1<<endl;
    return 0;
  }  
  if((x<0)&&(y==0)){
    cout<<abs(x)<<endl;
    return 0;
  }
  if((x>0)&&(y==0)){
    cout<<abs(x)+1<<endl;
    return 0;
  }
  
  if((x==0)&(y<0)){
    cout<<abs(y)+1<<endl;
    return 0;
  }
  if((x==0)&(y>0)){
    cout<<y<<endl;
    return 0;
  }
  if((x>0)&&(y<0)){
    cout<<abs(abs(y)-abs(x))+1<<endl;
    return 0;
  }  
  
  if(((x<0)&&(y<0))&&(abs(x)<abs(y))){
    cout<<abs(abs(y)-abs(x))+2<<endl;
    return 0;
  }  
  if(((x<0)&&(y<0))&&(abs(x)>abs(y))){
    cout<<abs(abs(y)-abs(x))<<endl;
    return 0;
  }  
  
  return 0;
}

    
    

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

using namespace std;
using ll = long long;

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

    }
    vector<ll> b(n);
    for(int i = 1;i < n;++i) {
        b[i]=a[i]-a[i-1];
        //cerr<<b[i]<<endl;
    }
    b[0]=a[0]+k-a[n-1];
    ll l=0;
    for(int i = 0;i < n;++i) {
        l=max(l,b[i]);
    }
    cout<<min(k-l,(k-l)*2)<<endl;
    return 0;
}


Measured memory_bytes: 3328
import java.util.Scanner

fun main() {
	val scn = Scanner(System.`in`)
	val n = scn.nextInt()
	val k = scn.nextInt()
	var ans = ModInt(0)
	for (i in k..n+1){
		ans += ModInt(n-i+1)*i + 1
	}
	println(ans)
}

class ModInt {
	var v: Long
		private set
	constructor(v: Int){
		this.v = when {
			v>=0 -> v.toLong() % MOD
			v==Int.MIN_VALUE -> 852516373
			else -> MOD.toLong() - (-v%MOD)
		}
	}
	constructor(v: Long){
		this.v = when {
			v>=0 -> v % MOD
			v==Long.MIN_VALUE -> 708828003
			else -> MOD - (-v%MOD)
		}
	}

	override fun toString() = v.toString()
	fun toInt() = v.toInt()
	fun toLong() = v
	override fun equals(other: Any?): Boolean {
		return if (other is ModInt) v == other.v else false
	}
	override fun hashCode() = 31*17 + v.hashCode()

	operator fun unaryPlus() = this
	operator fun unaryMinus() = ModInt(MOD-this.v)

	private operator fun plus(o: Long) = ModInt(this.v + o)
	operator fun plus(o: ModInt) = this.plus(o.v)
	operator fun plus(o: Int) = this.plus(o.toLong())
	private operator fun minus(o: Long) = this.plus(-o)
	operator fun minus(o: ModInt) = this.minus(o.v)
	operator fun minus(o: Int) = this.minus(o.toLong())
	private operator fun times(o: Long) = ModInt(this.v*o)
	operator fun times(o: ModInt) = this.times(o.v)
	operator fun times(o: Int) = this.times(o.toLong())
	private operator fun div(o: Long) = this.times(pow(o, MOD-2))
	operator fun div(o: ModInt) = this.div(o.v)
	operator fun div(o: Int) = this.div(o.toLong())

	operator fun inc() = this.plus(1)
	operator fun dec() = this.minus(1)

	companion object{
		const val MOD = 1000000007

		private fun pow(b:Long, e: Int): ModInt{
			if (b==1L) return ModInt(1)
			var ans = 1L
			var b = b; var e = e
			while (e!=0){
				if (e%2==1) ans = (ans*b)%MOD
				b = (b*b)%MOD
				e /= 2
			}
			return ModInt(ans)
		}
		fun pow(b: Int, e: Int): ModInt = pow(b.toLong(), e)
		fun pow(b: ModInt, e: Int): ModInt = pow(b.v, e)
	}
}

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

int main(){
    int n,x,t;
    cin >> n >> x >> t;
    int ans;
    if(n%x == 0){
        ans = (n/x)*t;
    }else{
        ans = (n/x + 1)*t;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3632
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

def gcd(a, b):
    if a == 0:
        return b
    else:
        return gcd(b%a, a)

def lcm(a, b):
    return a*b//gcd(a,b)
n, m = map(int, input().split())
a_array = np.array(list(map(int, input().split())))
c_array = np.copy(a_array)
while True:
    c_array //= 2
    if 1 in c_array%2:
        is_valid = not (0 in c_array%2)
        break
b_array = a_array//2
if is_valid:
    k = b_array[0]
    for i in range(n):
        k = lcm(k, b_array[i])
    ans = (m//k + 1)//2 
    print(ans)    
else:
    ans = 0
    print(ans)

Measured memory_bytes: 24272
N,M = map(int,input().split())
List = []
for i in range(M):
  List.append(0)
for k in range(N):
  tmp = list(map(int,input().split()))
  for n in range(tmp[0]):
    tmp2 = tmp[n+1]
    List[tmp2-1] += 1
print(str(List.count(N)))

Measured memory_bytes: 9184
N, K = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(N)]
P.sort()

ans = float('inf')
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        x = P[j][0] - P[i][0]
        if x == 0:
            continue

        Q = P[i: j + 1]
        Q.sort(key=lambda q: q[1])
        y = Q[-1][1] - Q[0][1]
        for k in range(0, len(Q) - K + 1):
            for l in range(k + K - 1, len(Q)):
                ny = Q[l][1] - Q[k][1]
                if ny == 0:
                    continue
                y = min(y, ny)
        ans = min(ans, x * y)

print(ans)


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

typedef pair<ll, ll> Pll;

ll mypow(ll a, ll b) {
    ll r = 1;
    while(b--) {
        r *= a;
    }
    return r;
}

int main() {
    int N; cin >> N;
    vector<Pll> ranges(40);
    ranges[0] = {1, 1}; ranges[1] = {-2, -1};
    for (int i = 2; i < 40; i++) {
        if (i % 2 == 0) {
            ranges[i] = {ranges[i-2].second+1, ranges[i-2].second+mypow(2, i)};
        } else {
            ranges[i] = {ranges[i-2].first-mypow(2, i), ranges[i-2].first-1};
        }
    }
    int i;
    for (i = 0; i < 40; i++) {
        if (ranges[i].first <= N && N <= ranges[i].second) break;
    }
    if (N == 0) i = 0;
    for (int j = i; 0 <= j; j--) {
        if (ranges[j].first <= N && N <= ranges[j].second) {
            cout << 1;
            if (j % 2 == 0) {
                N -= ranges[j].second - ranges[j].first + 1;
            } else {
                N += ranges[j].second - ranges[j].first + 1;
            }
        } else {
            cout << 0;
        }
    }
    cout << endl;
}


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

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

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

  ll ans = 0, cnt = 0;
  while(1){
    cnt += k;
    ans++;
    if(cnt >= n) break;
    cnt--;
  }

  cout << ans << endl;

  return 0;
}

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

int main() {
	int64_t n;
	cin >> n;
	int a = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)a = i;
	}
	cout << a - 1 + (n/a) - 1 << endl;
}


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

int main()
{
    int N;
    cin >> N;
    int a[N + 1];
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    a[N] = 0;
    sort(a, a + N);

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        cnt++;
        if (a[i] != a[i + 1])
        {
            if (cnt >= a[i])
            {
                ans += cnt - a[i];
            }
            else
            {
                ans += cnt;
            }
            cnt = 0;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 888
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
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(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

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

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			ans +=a[i]*a[j];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import           Control.Monad
import           Data.Array.Unboxed
import           Data.List.Split
import           Data.List
import           Data.Ord

main :: IO ()
main = do
  (cm : cs) <- sortOn Data.Ord.Down . map read . words <$> getLine
  putStrLn $ if cm == sum cs then "Yes" else "No"


Measured memory_bytes: 508
n,m=map(int,input().split())
arr=list(map(int,input().split()))
ans=0
for k in range(m):
  for i in range(m+1-k):
    j=m-k-i
    if i+j<=n:
      if j==0:
        tarr=arr[:i]
      else:
        tarr=arr[:i]+arr[-j:]
    else:
      tarr=arr[:]
    tarr=sorted(tarr)
    for l in range(min(len(tarr),k)):
      if tarr[l]<0:
        tarr[l]=0
    tsum=sum(tarr)
    ans=max(ans,tsum)
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
	
	int h,m,s,S;
	
	public void input(){
		Scanner sc = new Scanner(System.in);
		S = sc.nextInt();
	}
	
	public void hour(){
		if(S >=0 && S < 86400){
			h = S/3600;
		}
		else{
			System.out.print("error");
		}
	}
	
	public void minute(){
		if(S >=0 && S < 86400){
			m = (S-h*3600)/60;
		}
		else{
			System.out.print("error");
		}
	}
	
	public void second(){
		if(S >=0 && S < 86400){
			s = S-h*3600-m*60;
		}
		else{
			System.out.print("error");
		}
		System.out.println(h+":"+m+":"+s);
	}
	
	public static void main(String[] args){
		Main obj = new Main();
		obj.input();
		obj.hour();
		obj.minute();
		obj.second();
	}
}

Measured memory_bytes: 17360
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f;

using namespace std;

string s[200005];

/*bool cmp(string a,string b) {
        return a<b;
}*/

int main() {
    int n,i;
    scanf("%d",&n);
    for(i=0; i<n; i++)
        cin>>s[i];
    sort(s,s+n);
    int m=1,cnt=1;
    for(i=1; i<n; i++) {
        if(s[i]==(s[i-1]))
            cnt++;
        else
            cnt=1;
        m=max(cnt,m);
    }
    cnt=1;
    if(m==1)
        cout<<s[0]<<endl;
    for(i=1; i<n; i++) {
        if(s[i]==(s[i-1]))
            cnt++;
        else
            cnt=1;
        if(cnt==m)
            cout<<s[i]<<endl;
    }
}

Measured memory_bytes: 14208
/*input
4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 12;
const int M = 1e3+1;

int dp[1<<N][M];
int sos[1<<N];// includes answers for supermasks also
int cost[M];
int conf[M];
int n,m;

void solve(){
  	cin >> n >> m;
  	RE(i,m){
  		cin >> cost[i];
  		int sz;cin >>sz;
  		REP(j,sz){
  			int x;cin >> x;
  			conf[i] |= 1<<(x-1);
  		}
  	}
  	REP(i,1<<n){
  		REP(j,m+1){
  			dp[i][j] = INF;
  			sos[i] = INF;
  		}
  	}
  	sos[0] = 0;
  	dp[0][0] = 0;
  	RE(i,m){
  		REP(mask,1<<n){
 			//cout << mask << endl;
  			//cout << dp[mask][i-1] << endl;
  			int upd = mask|conf[i];
  			sos[mask|conf[i]] = min(sos[mask|conf[i]],dp[mask][i-1]+cost[i]);
  		}
  		for(int mask = (1<<n)-1;mask > 0;mask--){
  			REP(bit,n){
  				if( (1<<bit)&mask)sos[mask^(1<<bit)] = min(sos[mask],sos[mask^(1<<bit)]);
  			}
  		}

  		REP(mask,1<<n)dp[mask][i] = sos[mask];
  	}
  	if(dp[(1<<n)-1][m] == INF)cout << -1;
  	else cout << dp[(1<<n)-1][m];
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

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

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)
#define fcout cout << fixed << setprecision(10)

using namespace std;

int n, N, x;

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

    cin >> n >> x;
    N = 2 * n - 1;

    if (x == 1 || x == N) {
        cout << "No" << endl;
        return 0;
    }

    vector<int> v(N);
    set<int> s;

    v[N / 2] = x;
    s.insert(x);
    if (x + 1 == N) {
        v[N / 2 + 1] = x + 1;
        s.insert(x + 1);
        if (N > N / 2 + 2) v[N / 2 + 2] = x - 2;
        s.insert(x - 2);
        v[N / 2 - 1] = x - 1;
        s.insert(x - 1);
    } else {
        v[N / 2 + 1] = x - 1;
        s.insert(x - 1);
        if (N > N / 2 + 2) v[N / 2 + 2] = x + 2;
        s.insert(x + 2);
        v[N / 2 - 1] = x + 1;
        s.insert(x + 1);
    }

    int cur = 1;
    REP(i, N) {
        if (v[i] != 0) continue;
        while (s.count(cur) > 0) {
            cur++;
        }
        v[i] = cur;
        cur++;
    }

    cout << "Yes" << endl;
    REP(i, N) { cout << v[i] << endl; }

    return 0;
}


Measured memory_bytes: 3072
import java.util.Scanner;

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

        double[] means = new double[N];

        for (int i = 0; i < N; i++) {
            means[i] = (1.0d + sc.nextInt()) / 2;
        }
        double[] s = new double[N + 1];
        for (int i = 0; i < N; i++) {
            s[i + 1] = means[i] + s[i];
        }

        double max = 0;
        for (int i = 0; i + K <= N; i++) {
            double current = s[i + K] - s[i];
            if (max < current) {
                max = current;
            }
        }
        System.out.println(max);
    }
}


Measured memory_bytes: 83096
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#define pb push_back
#define mp make_pair
using namespace std;
const int N = 2e5 + 5;

int n;
long long a[N];

long long prefix[N];
map <long long,int> cnt;

long long ans;

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

   int i;

   cin >> n;
   for(i = 1; i <= n; i++)
   {
       cin >> a[i];
       prefix[i] = prefix[i - 1] + a[i];
   }

   cnt[0] = 1;
   for(i = 1; i <= n; i++)
   {    
       ans += cnt[prefix[i]];
       cnt[prefix[i]]++;
   }

   cout << ans << endl;


   return 0;
}

Measured memory_bytes: 15872
var n,l,r,x,y,mid:longint;
var s,ls:string;
begin
  readln(n);
  writeln(0);flush(output);readln(s);
  if s='Vacant' then exit else
  if ((s='Male') and ((n+1) mod 4>0)) or ((s='Female') and ((n+1) mod 4=0))
  then x:=0;ls:=s;
  writeln(n-1);flush(output);readln(s);
  if s='Vacant' then exit else
  if ((s='Male') and ((n+1) mod 4>0)) or ((s='Female') and ((n+1) mod 4=0))
  then x:=n-1;
  l:=0;r:=n-1;
  while s<>'Vacant' do
  begin
    mid:=(l+r)>>1;writeln(mid);flush(output);readln(s);
    if s='Vacant' then exit;     {
    if ((n+1) mod 4=0) then begin
    if ((s='Male') and (x<mid)) or ((s='Female') and (x>mid)) then
    begin r:=mid;if x<mid then x:=r;continue;end;
    if ((s='Male') and (x>mid)) or ((s='Female') and (x<mid)) then
    begin l:=mid;if x>mid then x:=l;end;
    end else begin
    if ((s='Male') and (x<mid)) or ((s='Female') and (x>mid)) then
    begin l:=mid;if x<mid then x:=l;continue;end;
    if ((s='Male') and (x>mid)) or ((s='Female') and (x<mid)) then
    begin r:=mid;if x>mid then x:=r;end;}
    if mid-1=l then begin l:=mid;ls:=s;continue;end;
    if mid+1=r then begin r:=mid;continue;end;
    if ((mid-1-l) mod 2=0) then
    begin
      if ls<>s then begin l:=mid;ls:=s;end
      else r:=mid;
    end else begin if ls<>s then r:=mid else begin ls:=s;l:=mid;end;end;
  end;
end.

Measured memory_bytes: 760
N, K = map(int, input().split())
X = list(map(int, input().split()))

ans = 10 ** 9
for i in range(N - K + 1):
    # # ２点間の距離
    d1 = X[i + K - 1] - X[i]
    # # ０からの距離
    d2 = min(abs(X[i + K - 1]), abs(X[i]))
    ans = min(ans, d1 + d2)

print(ans)


Measured memory_bytes: 14384
n = list(map(int, input().split()))
H, W = n[0], n[1]
li = [['.' for i in range(W)] for i in range(H)]

for i in range(H):
    l = input()
    for j in range(len(l)):
        li[i][j] = l[j]

pos = []
# horizontal check
for i in range(H):
    c = 0
    for j in range(W):
        if li[i][j] == '.':
            c += 1
    if c == W:
        pos.append(i)

j = 0
for i in range(len(pos)):
    li.pop(pos[i]-j)
    j += 1


pos = []
# vertical check
for i in range(len(li[0])):
    c = 0
    for j in range(len(li)):
        if li[j][i] == '.':
            c += 1
    if c == len(li):
        pos.append(i)

for i in range(len(li)):
    m = 0
    for x in range(len(pos)):
        li[i].pop(pos[x]-m)
        m += 1

for i in range(len(li)):
    print("".join(li[i]))


Measured memory_bytes: 3188
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n, m;
		int z = 8000000;
		while (true) {
			n = sc.nextInt();
			m = sc.nextInt();
			int num = n;
			if (n == 0) {
				break;
			}
			boolean[] check = new boolean[z];
			//true...以前の倍数
			//false...以前全てと互いに素
			for (int i = 0; i < m; i++) {//blockの数だけループ
				for (int j = num; j < z; j += num) {
					check[j] = true;
				}
				//n以上で初めてfalseであるcheckを探す
				//num = n;
				while (check[num]) {
					num++;
				} //END while
			} //END for(i)
			System.out.println(num);
		} //END while(true)
		sc.close();
	}
}



Measured memory_bytes: 53116
#include <iostream>
#include <string>
using namespace std;
int main(){
    int x;
    string s;
    cin >> x;
    cin >> s;
    int len = s.size();
    for(int i = 0; i < len; i ++){
        s[i] = 'A' + ((s[i] - 'A' + x) % 26);
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():
    N, M = map(int, input().split())


    S =[]
    C=[]
    for i in range(M):
        s,c=map(int,input().split())
        S.append(s)
        C.append(c)

    mini = 10**(N-1)
    if N==1:
        mini=0

    for i in range(mini,10**N):
        j = str(i)
        for k in range(M):
            s,c =S[k],C[k]
            if j[s-1]!=str(c):
                break
        else:
            print(i)
            exit()

    print(-1)






if __name__ == "__main__":
    main()


Measured memory_bytes: 63072