akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void)
{
  int n;
  scanf("%d", &n);
  int age, sute;
  age = (double)n / 1.08 + 0.99999;
  sute = n / 1.08;
  
  int tmp;
  tmp = sute * 1.08;
  if (tmp == n)
  {
    printf("%d", sute);
    return 0;
  }
  tmp = age * 1.08;
  if (tmp == n)
  {
    printf("%d", age);
    return 0;
  }
  printf(":(");
  return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

int main(){
  int n,a[200],i,cnt=-1,flag=1;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
while(flag){
cnt++;
  for(i=0;i<n;i++){
    if(a[i]%2==1)
      flag=0;
    a[i]/=2;
  }
}
  printf("%d\n",cnt);
}

Measured memory_bytes: 128
import numpy as np

pi = np.pi

a, b, x = map(int, input().split())

S = x/a

if S >= a*b/2:
    h = x/(a**2)
    ans = np.arctan((b - h)/(a/2)) / (2 * pi) * 360
elif S <= a*b/2:
    ans = np.arctan(b/(2*S/b)) / (2 * pi) * 360

print(ans)

Measured memory_bytes: 12484
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
constexpr auto INF = 2147483647;
constexpr auto MAX = 2000001;
constexpr auto VMAX = 10001;
typedef long long ll;

int A[MAX], B[MAX], C[VMAX];

void CountingSort(int n) {
	rep(i, VMAX) C[i] = 0;
	rep(i, n) C[A[i]]++;
	for (int i = 1; i < VMAX; i++) C[i] = C[i] + C[i - 1];
	for (int i = n; i >= 0; i--) {
		B[C[A[i]]-1] = A[i];
		C[A[i]]--;
	}
}

int main() {
	int n;
	cin >> n;
	rep(i, n) cin >> A[i];
	
	CountingSort(n);
	rep(i, n) {
		if (i) cout << " ";
		cout << B[i];
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 18752
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;

int main(){
    int x;
    cin >> x;
    int ans = (x / 500) * 1000;
    x %= 500;
    ans += (x / 5) * 5;
    cout << ans << endl;
    return 0;
}

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

int main(){
  int n,r;
  while(cin>>n>>r && n>0 && r>0){
    vector<int> v;
    for(int i=n;i>0;i--)v.push_back(i);
    while(r--){
      int p,c;
      cin>>p>>c;
      vector<int>::iterator it = v.begin();
      rotate(it,it+p-1,it+p+c-1);
    }
    cout<<v[0]<<endl;
  }
  return 0;
}

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

int main()
{
    int n; cin>>n;
    vector<int> c(n);
    for(auto e: c) {
        int a; cin>>a;
        if (++c[a]>1+(a>0) || a%2==n%2) return cout<<0<<endl, 0;
    }
    long res=1;
    for(int i=0; i<n/2; ++i) res=res*2%int(1e9+7);
    cout<<res<<endl;
}

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

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

    if( n % 10 == 7 || n / 10 % 10 == 7 || n / 100 % 10 == 7)
        cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
	char str[105];
	scanf("%s", str + 1);
	size_t length = strlen(str + 1);
	for (size_t i = 1; i <= length; i += 2)
	{
		if (str[i] != 'R' && str[i] != 'U' && str[i] != 'D')
		{
			puts("No");
			return 0;
		}
	}
	for (size_t i = 2; i <= length; i += 2)
	{
		if (str[i] != 'L' && str[i] != 'U' && str[i] != 'D')
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 256
/*
时间:2020-7-25
书籍：算法和数据结构
内容：冒泡排序
页数：P40
*/
#include<iostream>
using namespace std;
void printArray(int a[],int length)
{
	for (int i = 0; i < length - 1; ++i)
		cout << a[i] << " ";
	cout << a[length-1];                       //防止行元素后的空格多余导致PE
	cout << endl;                             //每一行结束输出要换行

}
void bubbleSort(int a[], int length)
{
	bool flag = true;               //排序提前完成时用来判断，避免不必要的比较。
	int temp=0;
	int count = 0;
	for (int i = 0; i < length && flag; ++i)
	{
		flag = false;                                          
		for (int j = 0; j < length - i - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				++count;
				flag = true;
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	printArray(a, length);
	cout << count << endl;
}
int main()
{
	int n;
	cin >> n;
	int* a = new int[n];
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	bubbleSort(a, n);
	delete[]a;
	return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 1<<17
int n,dat[2*(MAX_N)-1];
int valu[2*(MAX_N)-1];//更新順

//INT＿MAXで初期化
void init(int n_){
  n=1;
  while(n<n_)n*=2;
  for(int i=0;i<2*n-1;i++){
    dat[i]=INT_MAX;
    valu[i]=-1;
  }
}

//k番目の要素を返す
int find(int k){
  k+=n-1;
  int ans=dat[k];
  int va=valu[k];
  while(k>0){
    k=(k-1)/2;
    if(valu[k]>va){
      ans=dat[k];
      va=valu[k];
    }
  }
  return ans;
}

//[a,b)の範囲を更新
void update(int a,int b,int x,int i,int k=0,int l=0,int r=n){
  if(r<=a||b<=l)return; 
  if(a<=l&&r<=b){
    valu[k]=i;
    dat[k]=x;
  }else{
    update(a,b,x,i,k*2+1,l,(l+r)/2);
    update(a,b,x,i,k*2+2,(l+r)/2,r); 
  }
}

int main(){
  int q;
  cin>>n>>q;
  init(n);
  for(int i=0;i<q;i++){
    int com,s,t,x;
    cin>>com; //com=1でfind,elseでupdate
    if(com){
      cin>>s;
      cout<<find(s)<<endl;
    }else{
      cin>>s>>t>>x;
      update(s,t+1,x,i);
    }
  }
  return 0;
}



Measured memory_bytes: 5156
<?php
//$queueからarray_shift()でひとつ頭を取り出す。
//$ary[]に体節の並びを保持。体節の長さ分だけfor(foreach)でまわして $ary[$i] と $ary[$i+1] とを比較
//もし、色が違えば$queueに次階層の状態を追加($array_push)
//体節の色がすべて同じなら終了する。

$file_handle = fopen('php://stdin', "r");	//fopen()は同位フォルダにファイルがあればその名前のみでOK


//wfs
function wfs() {
	global $cnt;
	global $sec;
	global $ary_start;
	global $goal_flag;
	global $queue;

	$queue[0] = $ary_start;			//スタートを$queueに入れて開始
	$queue_size = count($queue[0]);	//キューの長さを取得
	$queue[0]['sec'] = 0;			//スタート時の秒数(階層の深さ)を入れる
	while (!empty($queue)) {		//$queueが1つ以上あればループ
	   $cur = array_shift($queue);	//配列$queueの頭から１つ取り出す。
	   
	   //終了条件。全ての配列が同じ色なら終了
	   $cnt = 0;	//カウントの初期化
	   for($i=0; $i<$queue_size; $i++){
	       if ($cur[$i] !== $cur[0]){ break; }
	       $cnt++;
	   }
	   if ($cnt === $queue_size) {
	       $goal_flag = 1;
	       $sec = $cur['sec'];	//ゴールした時の秒数
	       break;	//色がすべて同じならwhileを抜ける
	   }
	   
	   //探索
	    for($i=0; $i<$queue_size-1; $i++){
	    	if ($cur[$i] !== $cur[$i+1]){
    			$new = $cur;
    			$new['sec'] = $cur['sec'] + 1;
	    		if ($cur[$i] !== 'r' && $cur[$i+1] !== 'r'){	
	    			$new[$i] = 'r';  $new[$i+1] = 'r';
	    		} else if ($cur[$i] !== 'g' && $cur[$i+1] !== 'g'){
	    			$new[$i] = 'g';  $new[$i+1] = 'g';
	    		} else {
	    			$new[$i] = 'b';  $new[$i+1] = 'b';
	    		}
	    		$str = toString($new);
	    		if (empty($visited[$str])){
		    		array_push($queue, $new);
				    $visited[$str] = 1;
				}
	    	}
	    }
	}
}

//再訪防止用。配列のキーに文字列を設定するために使用
function toString($ary){
	$str = '';
	foreach ($ary as $key => $val){
		if (is_numeric($key)) {	
			$str = $str.$val;
		}
	}
	return $str;
}


while (1){
	//変数の初期化
	$cnt = 0;	//終了条件に使用
	$sec = 0;
	$goal_flag = 0;
	$queue = array();

	//ファイル読み込み
	$stdin = trim(fgets($file_handle));
	//終了条件
	if ($stdin == '0'){
		break;
	}
	$ary_start = str_split($stdin);
	

	//探索
	wfs();

	//出力
	if ($goal_flag === 1){
		echo $sec;
	} else {
		echo 'NA';
	}
	echo PHP_EOL;
}

fclose($file_handle);

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

#define rep(i, n) for (ll i=0;i<(n); 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; }
#define ALL(x) (x).begin(),(x).end()
#define Sort(a) sort(ALL(a))
#define Rev(a) reverse(ALL(a))


using namespace std;
//using ll=long long;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;
const long double PI=3.14159265358979323846;


template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}


int main(){

  ll n;
  cin>>n;

  ll s=0;
  vector<ll> a(n+2);
  rep(i,n){
    cin>>a[i+1];
    s+=abs(a[i+1]-a[i]);
  }
  a[n+1]=0;
  s += abs(a[n+1]-a[n]);
  rep(j,n){
    ll i = j+1;
    cout<<s+abs(a[i-1]-a[i+1])-abs(a[i-1]-a[i])-abs(a[i+1]-a[i])<<endl;
  }
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <fstream>
#include <set>
#include <stack>
#include <queue>
#include <list>
using namespace std;
typedef long long int64;
typedef vector<int> vec;
typedef vector<int64> vec64;
#define db(x) cout << "> " << #x << ": " << x << "\n";
#define ss cout << " ";
#define ct(x) cout << x;
#define nn cout << "\n";
#define cts(x) cout << x << " ";
#define ctn(x) cout << x << "\n";
#define qr queries();
void solve();
void YN(bool b){if (b){ctn("YES");}else{ctn ("NO");}};
void yn(bool b){if (b){ctn("Yes");}else{ctn ("No");}};
void queries(){int n;cin >> n;while (n--)solve();}
// // // // // // // // // // // // // // // // // // // // // // 
/*                  TEMPLATE - VANILLA                         */
// // // // // // // // // // // // // // // // // // // // // //
int n,m,k;
int64 f = 0;
vector <string> mat (10);
bool b[10];
bool v[10];

void backtrack2(int step){
    if (step == m){
        solve();
        return;
    }
    v[step] = 1;
    backtrack2(step+1);
    v[step] = 0;
    backtrack2(step+1);
}

void backtrack(int step){
    if (step == n){
        backtrack2(0);
        return;
    }
    b[step] = 1;
    backtrack(step+1);
    b[step] = 0;
    backtrack(step+1);
}

void solve(){
    vector <string> mat2 = mat;
    for (int i = 0; i < n; i++){
        if (b[i]){
            for (int j = 0; j < m; j++){
                mat2[i][j] = '-';
            }
        }
    }
    for (int i = 0; i < m; i++){
        if (v[i]){
            for (int j = 0; j < n; j++){
                mat2[j][i] = '-';
            }
        }
    }
    int rs = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            // ct(mat2[i][j]);
            if (mat2[i][j] == '#'){
                rs++;
            }
        }
        // nn;
    }
    // db(rs);
    if (rs == k){
        f++;
    }
    // nn;
}


int main(){
    cin >> n >> m >> k;
    for (int i = 0; i <n; i++){
        cin >> mat[i];
    }
    backtrack(0);
    ctn(f);
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <string>

int main(){
  std::string S;
  std::cin >> S;
  long int N = S.size();
  long int count = 0;
  for(int i=0; i < N/2; ++i){
    if(S[i] != S[N-i-1]) count++;
  }
  std::cout << count << std::endl; 
  return 0;
}


Measured memory_bytes: 256
import sys
import math
 
input = sys.stdin.readline
 
K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        n = math.gcd(i, j)
        for l in range(1, K + 1):
            ans += math.gcd(n, l)
 
print(ans)

Measured memory_bytes: 67768
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }

ll N = 1e9;
ll ans;
 
void dfs(ll K, bool flag7, bool flag5, bool flag3){
	if (K>N) return;
	// if (flag7 & flag5 & flag3) cout << 1 << endl;
	if (flag7 & flag5 & flag3) ans++;
	dfs(K*10+7, true, flag5, flag3);
	dfs(K*10+5, flag7, true, flag3);
	dfs(K*10+3, flag7, flag5, true);
    return;
}

int main() {
	// 入力
	cin >> N;
 
	// 解法
	dfs(0, false, false, false);
	
	cout << ans << endl;
}


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

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define for1(i, a, b) for (int i = (int)a; i < (int)(b); ++i)
#define rfor1(i, a, b) for (int i=(int)b-1;i>=(int)a;i--)
#define for2(i, a, b) for (int i = (int)a; i <= (int)(b); ++i)
#define for3(i, a, b) for (int i = (int)a; i < (int)(b); i=i+2)
#define for4(i, a, b) for (int i = (int)a; i <= (int)(b); i=i+2)
#define tc(t) int t; cin>>t; while(t--)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x; cin >> x;
    if(x >= 30) {
        cout << "Yes" << "\n";
    }
    else {
        cout << "No" << "\n";
    }
}









Measured memory_bytes: 3660
# :colon
import math
A,B,H,M = map(int,input().split())

def get_theta(h,m):
		cand = abs(m*6 - (h*30 + m*0.5))
		theta = math.radians([cand, 360 - cand][cand > 180])
		return theta

def cos_thm(a,b,theta):
		c_squared = (a**2) + (b**2) - (2*a*b*math.cos(theta))
		return math.sqrt(c_squared)

theta = get_theta(H,M)
if theta == 0:
		ans = abs(A-B)
elif theta == 180:
		ans = A+B
else:
		ans = cos_thm(A,B,theta)

print(ans)

Measured memory_bytes: 9408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  int cur = 1;
  int t = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == 'a') {
      if (t < a + b) {
	puts("Yes");
	t++;
      } else {
	puts("No");
      }
    } else if (s[i] == 'b') {
      if (t < a + b && cur <= b) {
	puts("Yes");
	t++;
	cur++;
      } else {
	puts("No");
      }
    } else {
      puts("No");
    }
  }
  return 0;
}


Measured memory_bytes: 896
#include <stdio.h>

int main()
{
    long long n,a[100000],b[100000],count = 0,i;

    scanf("%lld",&n);
    for (i = 0; i < n; i++)
    {
        scanf("%lld %lld",&a[i],&b[i]);
    }

    for (i = n - 1; i >= 0; i--)
    {
        a[i] += count;
        if(a[i] % b[i] != 0)
        {
            count += b[i] - a[i] % b[i];
        }
    }
    
    printf("%lld",count);
}

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

m = max(a)
#約分できちゃう数値リスト
lis = [0]*(m + 1)
for i in a:
  for j in range(i, m + 1, i):
    lis[j] += 1
#iが1なら、lisの要素全てに+1されてる。
count = 0
for i in a:
  if lis[i] == 1:
    count += 1
    
print(count)

Measured memory_bytes: 32236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, INF = 0x3f3f3f3f, M = N << 1;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define repe(i, u) for (int i = head[u]; i; i = nxt[i])

ll n;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  ll ans = 0;
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  n--;
  cout << (n + 1) * n / 2 << endl;
}

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

#define ll long long

using namespace std;
const int OO = 0x3f3f3f3f, MOD = 1000000007;

int arr[100005][4];
int mem[100005][4] = {};
int n;

int solve(int idx = 0, int lastChoice = 0)
{
    int& ret = mem[idx][lastChoice];

    if(~ret) return ret;
    if(idx >= n) return ret = 0;

    for(int i = 1; i < 4; i++)
    {
        if(i == lastChoice) continue;
        ret = max(ret, solve(idx + 1, i) + arr[idx][i]);
    }

    return ret;
}

int main()
{
    //freopen ("out.txt","w",stdout);

    cin >> n;
    memset(mem, -1, sizeof mem);
    for(int i = 0;i < n; i++)
        cin >> arr[i][1] >> arr[i][2] >> arr[i][3];

    cout << solve();

	return 0;
}


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

int A, B;

int main() {
    cin >> A >> B;

    if (B % A == 0) {
        printf("%d\n", A + B);
    } else {
        printf("%d\n", B - A);
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const ll mod = 1e9+7;
const int inf = INT_MAX-100;
//int dp[100000+1];
void solve(){
	int i, n;
	cin>>n;
	int arr[n];
	vector<int> dp(n, inf);
	for(i=0;i<n;i++){
		cin>>arr[i];
	}
	dp[0]=0;
	for(i=0;i<n;i++){
		for(int j=1;j<=2;j++){
			if(i+j <n){
				dp[i+j]=min(dp[i+j], dp[i]+abs(arr[i+j]-arr[i]));
			}
		}
	}
	cout<<dp[n-1]<<endl;
}

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

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

int main() {
  int K,X;
  cin >> K>>X;
  for(int i=X-K+1;i<=X+K-1;i++){
    if(i==X+K-1)cout<<i<< endl;
    else cout<<i<<" ";
  }

  }


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

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    int r, g; cin >> r >> g;
    if (r <= g) cout << g + g - r << endl;
    else
    {
        cout << g - (r - g) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IL inline
#define RG register
#define gi geti<int>()
#define gl geti<ll>()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>
IL T geti()
{
	RG T xi=0;
	RG char ch=gc;
	bool f=0;
	while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
	while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
	return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
	if(k<0)k=-k,putchar('-');
	if(k>=10)pi(k/10);
	putchar(k%10+'0');
	if(ch)putchar(ch);
}
/*
IL unsigned int LOG2(unsigned int x)
{
	unsigned int ret;
	__asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
	return ret;
}
*/
#define count __builtin_popcount
#define lg2(x) (31-__builtin_clz(x))
#define lowbit(x) ((x)&(-(x)))
const int N=15,M=1<<N,P=1e9+7;
int f[M],g[N],pw[M];
int main(void)
{
	#ifndef ONLINE_JUDGE
//	File("");
	#endif
	pw[0]=f[0]=1;
	int n=gi,m=gi;
	for(int i=1;i<=m;++i)pw[i]=(pw[i-1]<<1)%P;
	for(int i=1;i<=m;++i){
		int u=gi-1,v=gi-1;
		g[u]|=1<<v;
	}
	for(int s=1;s<(1<<n);++s)//枚举总点集
		if((s&1)==(s>>1&1))
		for(int x=s;x;x=(x-1)&s)
			if((x&1)==(x>>1&1))
			{
				int y=s^x;
				ll ans=1;
				for(int ts=s;ts;ts^=lowbit(ts))
				{
					int val=lowbit(ts),i=lg2(val);
					if(x&val)(ans*=pw[count(g[i]&y)])%=P;
					else (ans*=pw[count(g[i]&x)]-1)%=P;
				}
				(f[s]+=f[y]*ans%P)%=P;
			}
	pi((pw[m]-f[(1<<n)-1]+P)%P);
	return 0;
}


Measured memory_bytes: 384
from bisect import bisect


N, M, K = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())

a_cum = [0]
cum = 0
for x in A:
  cum += x
  a_cum.append(cum)
  
b_cum = []
cum = 0
for x in B:
  cum += x
  b_cum.append(cum)
  
answer = 0

for i, a in enumerate(a_cum):
  remain = K - a
  if remain < 0:
    break

  t = bisect(b_cum, remain)
  # print('remain', remain, 't', t)
  answer = max(answer, i + t)
  
      
print(answer)    

Measured memory_bytes: 115624
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(), (a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(), (a).end())
map<int,int64_t> p;
//(O(n))
//素因数分解
void fl(int64_t n){
    if(n==1){
        return ;
    }
    int tmp = n;
    while(tmp%2==0 ){
        tmp /= 2;
        p[2]++;
    }
    for(int i=3;i*i<=tmp;i++){
        while(tmp % i ==0){
            tmp /= i;
            p[i]++;
        }
    }
    if(tmp!=1){
        p[tmp]++;
    }
}
int main(){
    int64_t n;
    cin>>n;
    //(O(n));
    for(int i=1;i<=n;i++){
        fl(i);
    }
    int64_t ans = 1;
    for(auto c:p){
        int g = c.first;
        int64_t sh = c.second;
        if(g!=1){
            ans = ans*(sh+1)%big; 
        }
        //cout<<g<<"^"<<sh<<endl;
    }
    cout<<ans<<endl;
}

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

int N, M, a[100005];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i != M; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		++a[x]; ++a[y];
	}
	for (int i = 2; i <= N; ++i) {
		if (a[i] & 1) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}


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

typedef long long ll;
int a[200005];

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

  int k = 1;
  for(int i = 0; i < n; i++) {
    while(i < n && a[i] != k) {
      i++;
    }
    if(i == n) break;
    k++;
  }
  if(k == 1) {
    cout << -1 << endl;
    return 0;
  }

  cout << n - (k - 1) << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int ans=1;
  n-=k;
  if(n%(k-1)==0){
    ans+=n/(k-1);
  }
  else{
    ans+=(n-(n%(k-1)))/(k-1);
    ans++;
  }
  cout<<ans;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		while(in.hasNext())
		{
			int n=in.nextInt();
			int root[][]=new int[n+1][n+1];
			for(int i=0;i<=n;i++)
				Arrays.fill(root[i], 10000);
			for(int i=0;i<n;i++)
			{
				int r=in.nextInt();
				int k=in.nextInt();
				for(int j=0;j<k;j++)
					root[r][in.nextInt()]=1;
			}
			for(int i=0;i<=n;i++)
				root[i][i]=0;
			for (int i=1;i<=n;i++)//ワーシャルフロイド
				for(int j=1;j<=n;j++)
					for(int k=1;k<=n;k++)
					{
						//j->kへ行くのにiを経由した方が良いかどうか
						int c=root[j][i]+root[i][k];
						root[j][k]=Math.min(root[j][k],c);
					}
			int p=in.nextInt();
			for(int i=0;i<p;i++)
			{
				int s=in.nextInt(),t=in.nextInt();
				int TTL=in.nextInt();
				int min=root[s][t]+1;
				System.out.println(min<=TTL ? min:"NA");
			}
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 2000000001;
constexpr ll INF= 9 * 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

ll PP(ll a,ll b) {
    ll ret = 1;
    for(ll i = 0;i < b;i++) {
        ret *= (a - i);
        ret %= MOD;
    }
    return ret;
}

ll N,K;
vector<int> graph[100010];
bool used[100010];
ll ret = 1;

void dfs(int a) {
    ll cnt = 0;
    used[a] = true;
    for(int i = 0;i < graph[a].size();i++) {
        if(used[graph[a].at(i)] == false) {
            cnt++;
            dfs(graph[a].at(i));
        }
    }
    if(a == 0) {
        ret = ret * PP(K - 1,cnt);
        ret %= MOD;
    }
    else {
        ret = ret * PP(K - 2,cnt);
        ret %= MOD;
    }
    return;
}

int main() {
    cin >> N >> K;
    for(int i = 0;i < N - 1;i++) {
        int A,B;
        cin >> A >> B;
        A--;
        B--;
        graph[A].push_back(B);
        graph[B].push_back(A);
    }
    used[0] = true;
    dfs(0);
    cout << K * ret % MOD << endl;
}

Measured memory_bytes: 9344
n = int(input())
al=[chr(ord('a') + i) for i in range(26)]
A = [list(input()) for i in range(n)]
ans = ''
for i in range(26):
  st = al[i]
  cn = 50
  for j in range(n):
    cn=min(A[j].count(st),cn)
  ans += st*cn
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cmath>
 
#define pai 3.141592653
 
using namespace std;
 
int main(void)
{
    double a, b, C;
    double S, L, h;
    double c;
 
    cin >> a >> b >> C;
 
    h = b * sin(pai / 180 * C);
    c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(pai / 180 * C));
 
    S = a * h / 2;
    L = a + b + c;
 
    printf("%f\n", S);
    printf("%f\n", L);
    printf("%f\n", h);
 
    return 0;
}

Measured memory_bytes: 1232
function Main(input) {
  input = input.split("\n");
  var h = parseInt(input[0].split(" ")[0]);
  var w = parseInt(input[0].split(" ")[1]);
  var n = parseInt(input[1]);
  tmp = input[2].split(" ");
  a=new Array(n).fill(0);
  for(i=0;i<n;i++){
    a[i]=parseInt(tmp[i]);
  }
  var ans ="";
  c = new Array(h).fill(0);
  for(i=0;i<h;i++){
    csub = new Array(w).fill(0);
    c[i]=csub;
  }
  d = new Array();
  for(i=0;i<n;i++){
    for(j=0;j<a[i];j++){
      d.push(i+1);
    }
  }
  for(i=0;i<h;i++){
    if(i%2!=1){
      for(j=0;j<w;j++){
        c[i][j]=d[i*w+j];
      }
    }else{
      for(j=0;j<w;j++){
        c[i][j]=d[(i+1)*w-j];
      }
    }
  }
  for(i=0;i<h;i++){
    if(i%2!=1){
      for(j=0;j<w;j++){
        if(j%w!=w-1){
        ans+=d[i*w+j]+" ";
        }else{
        ans+=d[i*w+j]+"\n";
        }
      }
    }else{
      for(j=0;j<w;j++){
        if(j%w!=w-1){
        ans+=d[(i+1)*w-j-1]+" ";
        }else{
          ans+=d[(i+1)*w-j-1]+"\n";
        }
      }
    }
  }
  ans=ans.substr(0,ans.length-1);
  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 9264
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int max = Math.max(x,y);
        int min = Math.min(x,y);
        
        int ansA = a * x + b * y;
        int ansB = 2 * c * min + a * (x-min) + b * (y-min);
        int ansC = 2 * c * max;
        int ans = Math.min( Math.min(ansA,ansB),ansC );
        System.out.println(ans);
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  vector<int>N(S.size());
  for (int i = 0; i < S.size(); i++) {
    N.at(i) = S.at(i) - '0';
  }
  
  int count = 0;
  for (int i = 0; i < S.size(); i++) {
    if (i == 0){
      if (N.at(i) != 17){
        cout << "WA" << endl;
        return 0;
      }
    }
    else if (i == 1 || i == S.size() - 1){
      if (N.at(i) < 49){
        cout << "WA" << endl;
        return 0;
      }
    }
    else {
      if (N.at(i) == 19){
        count++;
      }
      else if (N.at(i) < 49){
        cout << "WA" << endl;
        return 0;
      }
    }
  }
  
  if (count == 1){
    cout << "AC" << endl;
  }
  else {
    cout << "WA" << endl;
  }
}
      
  



Measured memory_bytes: 3612
A = []
for i in range(3):
    A.append(list(map(int, input().split(' '))))
N = int(input())

for i in range(N):
    b = int(input())
    for I in range(3):
        for J in range(3):
            if A[I][J] == b:
                A[I][J] = 0

bingo = False
#print(*A, sep='\n')
#print(A[0][:])
#print(A[:][0])
# 横
#print('i')
for i in range(3):
    #print(i, A[i][:])
    if A[i][:] == [0, 0, 0]:
        bingo = True
# 縦
#print('j')
for j in range(3):
    #print(j, [A[0][j], A[1][j], A[2][j]])
    if [A[0][j], A[1][j], A[2][j]] == [0, 0, 0]:
        bingo = True

# 斜め
#print('h')
#print([A[0][0], A[1][1], A[2][2]])
if [A[0][0], A[1][1], A[2][2]] == [0, 0, 0]:
    bingo = True

#print('g')
#print([A[0][2], A[1][1], A[2][0]])
if [A[0][2], A[1][1], A[2][0]] == [0, 0, 0]:
    bingo = True

if bingo == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3188
import java.util.Scanner

object Main{
  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    val Array(a, b) = sc.nextLine.split(" ").map(_.toInt)
    if (b % a == 0) println(a + b)
    else println(b - a)
  }
}

Measured memory_bytes: 27440
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

struct Dice{
	int me[6];
	Dice(int a[6]){
		for (int i = 0; i < 6; i++){
			me[i] = a[i];
		}
	}
	bool check(Dice d2){
		for (int i = 0; i < 6; i++){
			if (d2.me[i] != me[i])return false;
		}
		return true;
	}
	void print(){
		for (int i = 0; i < 6; i++){
			cout << me[i] << " ";
		}
		cout << endl;
	}
};

int a[6], q;

int main(){
	REP(i, 6)cin >> a[i];
	Dice d1(a);
	REP(i, 6)cin >> a[i];
	Dice d2(a);
	bool f = 0;
	REP(i, 4){
		REP(j, 4){
			if (d1.check(d2))f = 1;
			swap(d1.me[1], d1.me[2]);
			swap(d1.me[2], d1.me[4]);
			swap(d1.me[4], d1.me[3]);
		}
		REP(j, 4){
			if (d1.check(d2))f = 1;
			swap(d1.me[0], d1.me[1]);
			swap(d1.me[1], d1.me[5]);
			swap(d1.me[5], d1.me[4]);
		}
		swap(d1.me[0], d1.me[2]);
		swap(d1.me[2], d1.me[5]);
		swap(d1.me[5], d1.me[3]);
	}
	if (f)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int64_t ans = -LINF;
	int a, b, c, k; cin >> a >> b >> c >> k;
	int64_t tmp = 0;
	tmp += min(k, a);
	k -= a;
	k -= b;
	if(k > 0) {
		tmp -= min(k, c);
	}
	cout << tmp << '\n';
	return 0;
}

Measured memory_bytes: 3632
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
bM = math.ceil(b)
Bm = [abs(x - bm) for x in B]
BM = [abs(x - bM) for x in B]
m = sum(Bm)
M = sum(BM)
print(int(min([m,M])))

Measured memory_bytes: 36780
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef map< string, vector< string > > Graph;
typedef long long int64;

Graph graph;
int N;
map< string, int > food;
map< string, int > dp;
map< string, bool > v;
const int INF = 1 << 30;


void solve(string S, int value) {
  if(v[S]++) return;
  value = min(food[S], value);
  food[S] = value;
  for(int i = 0; i < graph[S].size(); i++) {
    solve(graph[S][i], value);
  }
}


signed main() {
  cin >> N;

  vector< pair< int, string > > stack;
  for(int i = 0; i < N; i++) {
    string a;
    int x;
    cin >> a >> x;
    food[a] = x;
    stack.push_back(make_pair(x, a));
  }
  sort(stack.begin(), stack.end());

  int M;
  cin >> M;
  for(int i = 0; i < M; i++){
    string s, t;
    cin >> s >> t;
    graph[s].push_back(t);
    graph[t].push_back(s);
  }
  int64 ret = 0LL;
  for(vector< pair< int, string > >::iterator it = stack.begin(); it != stack.end(); ++it){
    solve(it -> second, it -> first);
  }
  for(map< string, int >::iterator it = food.begin(); it != food.end(); ++it){
    ret += it -> second;
  }
  cout << ret << endl;
}

Measured memory_bytes: 2624
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;

/* ---------- Constants  */
const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

int V, E;
const int MAX_V = 100000;

struct edge {
    int to;
    ll yen;
    ll sunuk;
};

vector<edge> G[MAX_V];
ll d_yen[MAX_V];
ll d_sunuk[MAX_V];

#define P pair<ll, int>

void dijkstra(int v, string type) {
    priority_queue<P, vector<P>, greater<>> que;
    que.push(P(0, v));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (type == "yen") {
            if (p.first > d_yen[v]) continue;
        } else {
            if (p.first > d_sunuk[v]) continue;
        }

        for (int i = 0; i < G[v].size(); i++) {
            if (type == "yen") {
                if (d_yen[G[v][i].to] > d_yen[v] + G[v][i].yen) {
                    d_yen[G[v][i].to] = d_yen[v] + G[v][i].yen;
                    que.push(P(d_yen[G[v][i].to], G[v][i].to));
                }
            } else {
                if (d_sunuk[G[v][i].to] > d_sunuk[v] + G[v][i].sunuk) {
                    d_sunuk[G[v][i].to] = d_sunuk[v] + G[v][i].sunuk;
                    que.push(P(d_sunuk[G[v][i].to], G[v][i].to));
                }
            }
        }
    }
}

int main() {
    cin >> V >> E;
    int s, t;
    cin >> s >> t;
    s--; t--;

    for (int i = 0; i < E; i++) {
        int u, v;
        ll a, b;
        cin >> u >> v >> a >> b;
        u--; v--;

        G[u].push_back({v, a, b});
        G[v].push_back({u, a, b});
    }

    fill(d_yen, d_yen + V, INF);
    fill(d_sunuk, d_sunuk + V, INF);

    d_yen[s] = 0;
    d_sunuk[t] = 0;

    dijkstra(s, "yen");
    dijkstra(t, "sunuk");

    ll ret = INF;
    ll base = (ll) pow(10, 15);
    vector<ll> ans;
    for (int i = V - 1; i >= 0; i--) {
        ret = min(ret, d_yen[i] + d_sunuk[i]);
        ans.push_back(base - ret);
    }

    reverse(ans.begin(), ans.end());

    for (ll a : ans) {
        cout << a << endl;
    }

    return 0;
}

Measured memory_bytes: 13952
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
using namespace std;
int n,a[N+5];char s[N+5];
int main()
{
	RI i;for(scanf("%d%s",&n,s),--n,i=0;i^n;++i) a[i]=abs(s[i]-s[i+1]);
	RI f=1;for(i=0;i^n;++i) if(a[i]==1) {f=0;break;}
	for(i=0;i^n;++i) a[i]==2&&(a[i]=f);
	RI ans=0;for(i=0;i^n;++i) (((n-1)^i)==(n-1)-i)&&(ans^=a[i]);
	return printf("%d",ans*(f+1)),0;
}

Measured memory_bytes: 5120
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const L = parseInt(arg[0].split(" ")[1]);
    
    let list = [];
    
    
    for(let i=0; i<N; i++) {
        let taste = (L + (parseInt(i) + 1)) - 1;

        list.push(taste);
    }
    
    let max = list.reduce((m,n)=>m+n);
    let min = Infinity;
    let target;
    
    for(let i=0; i<N; i++) {
        let temp = max - list[i];
        let abs  = Math.abs(max - temp);
        
        if(abs < min) {
            min = abs;
            target = i;
        }

    }
    list.splice(target, 1);
    
    console.log(list.reduce((m,n)=>m+n));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

int main(){
  int N;cin>>N;
  vector<int> d(N);
  
  rep(i,N) cin>>d[i]; 
  
  sort(d.begin(),d.end());
  
  int cnt=0;
 
  rep(i,N-1){
    if(d[i]<d[i+1]) cnt++;
  }
  cout<<cnt+1<<endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 600;
const int MOD = 1e9 + 7;
 
int n, k, tot = 0, _left, a[N]; 
ll ans = 0, c[N][N]; 

inline ll add( ll a, ll b ) { ll ret = a + b; if( ret > MOD ) ret -= MOD; return ret; }

inline void init_c( int size ) 
{
	for( int i = 0; i <= size; i ++ )
	{
		c[i][0] = 1;
		for( int j = 1; j <= i; j ++ )
			c[i][j] = add( c[i-1][j], c[i-1][j-1] );
//		printf( "C(5, 3) = %lld\n", c[5][3] );
	}
} 

string opt;

inline bool check()
{
	if( !tot ) return false;
	
	int now1 = 1, now2 = 1, c = 0;
	// now1: 红色生成到的段
	// now2: 蓝色生成到的段 
	// c: 剩余需要的 划分成段的 数量 
	
	for( int i = 1; i <= k; i ++ )
	{
		if( now1 > tot && a[now2] <= 1 && !c ) return true;
		// 优先生成新的段 
		if( now1 <= tot && opt[i-1] == 'r' ) ++ now1;
		// 优先满足大的 
		// 如果a[now2] <= 1 说明对于所有的 i >= now2, 都满足a[i] <= 1 
		else if( now2 < now1 && a[now2] > 1 && opt[i-1] == 'b')	
			c += a[now2] - 2, now2 ++;
		// 如果蓝色和红色都不需要生成新的段，则用来填补以前的段 
		else if( c ) c --;
	}
	
	return now1 > tot && a[now2] <= 1 && !c; 
}

inline void update()
{
	ll res = 1; int num = tot + 1;
	
	int next = 1;
	for( int i = 1; i <= tot; i = next + 1 )
	{
		next = i; 
		while( a[next+1] == a[i] )
			next ++;
		
		res = res * c[next][i-1] %MOD;
		// 相当于在 i 个空中插入 next-i+1 个相同的球 
		num += ( next - i + 1 ) * ( ( a[i] << 1 ) -1 );
	} 
	
	res = res * c[num-1+_left][num-1] %MOD;
	ans = add( ans, res );
	
//	printf( "[UPD] left:%d, num:%d, res:%lld\n", _left, num, res );
}

void dfs( int u ) 
// 有序的枚举 
{
	if( _left < 0 ) return;
	if( check() ) update();

	if( tot ) _left --; tot ++;
	
	_left --; dfs( a[tot] = 1 ); _left ++;
	
	for( int i = 2; i <= u; i ++ )
	{
		_left -= ( i << 1 ) - 3;
		dfs( a[tot] = i ); 
		_left += ( i << 1 ) - 3; 
	}
	
	a[tot--] = 0;
	if( tot ) _left ++;
}
 
int main()
{
	scanf( "%d%d", &n, &k );
	init_c( 500 );
	
	cin>> opt;
	_left = n; dfs( 100 );
	
	printf( "%lld\n", add( ans, 1 ) );
	
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int N = 1e3 + 5 ;

struct tower{
    ll w , s , v ;
    tower(ll w = 0, ll s = 0, ll v = 0) : w(w), s(s), v(v) {}
    inline void read(){
        scanf("%lld %lld %lld" , &w , &s ,&v);
    }
    inline bool operator < (const tower &p){
        return ((p.w + p.s) > (w + s));
    }
};
tower t[N];
int n;
ll dp[1000+5][100000+4];
bool memoize[1000+5][100000+4];
inline ll solve(int pos, ll weight)
{
      if (pos > n) return 0;
      if (weight > 10000) return 0;
      ll &ret = dp[pos][weight];
      bool &mem = memoize[pos][weight];
      if (mem) return ret;
      mem = 1;
      ret = 0;
      if (weight <= t[pos].s)
      {
            ret = max(ret, t[pos].v + solve(pos+1, weight + t[pos].w));
      }
      ret = max(ret, solve(pos+1, weight));
      return ret;
}
int main(){


    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; ++i){
        t[i].read();
    }
    sort(t + 1 , t + n + 1);
    
    printf("%lld", solve(1, 0));

    return 0;
}


Measured memory_bytes: 879104
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll  long long 
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e6+9;
const ll MOD=998244353;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
ll cnt[MAX];
int main() 
{

	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int n;
    cin>>n;
    ll arr[n+1];
    ll ans=0;
    for(int i=1;i<=n;i++){
      cin>>arr[i];
      cnt[arr[i]]++;
      ans+=arr[i];
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
      ll a, b;
      cin>>a>>b;
      ll u=cnt[a]*a;
      ans=ans-u;
      ans=ans-b*cnt[b];
      cnt[b]+=cnt[a];
      cnt[a]=0;
      ans=ans+b*cnt[b];
      cout<<ans<<endl;
    }


}

Measured memory_bytes: 5140
n = int(input())
lst = list(map(int,input().split()))
ans = 10000000000000
for i in range(1,n):
  #print(lst[:i],lst[i:])
  ans2 = abs(sum(lst[:i])-sum(lst[i:]))
  #print("ans2="+str(ans2))
  if ans2 < ans:
    ans = ans2
print(ans)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var str = ReadLine();
        var acgt = "ACGT";
        var res = 0;
            var ct = 0;
            for (var j = 0; j < str.Length; j++)
                if (acgt.Contains(str[j])) ct++;
                else
                {
                    res = Max(ct, res);
                    ct = 0;
                }
        WriteLine(Max(ct,res));
    }
}


Measured memory_bytes: 13268
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int h = sc.nextInt();
      int w = sc.nextInt();
      String[][] grid = new String[h][w];
      int[] ph = new int[h];
      int[] pw = new int[w];
      for(int i = 0;i < h;i++){
        String str = sc.next();
      	for(int j = 0;j < w;j++){
          grid[i][j] = str.substring(j,j+1);
          if(grid[i][j].equals("#")){
          	ph[i]++;
            pw[j]++;
          }
          
        }
      }
      for(int i = 0;i < h;i++){
      	for(int j = 0;j < w;j++){
        	if(ph[i] > 0 && pw[j] > 0){
            	System.out.print(grid[i][j]);
            }
        }
        if(ph[i] > 0){
        	System.out.println("");
        }
      }
    }
}


Measured memory_bytes: 24164
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
#include <vector>
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define base10_4 10000      //1e4
#define base10_5 100000     //1e5
#define base10_6 1000000    //1e6
#define base10_7 10000000   //1e7
#define base10_8 100000000  //1e8
#define base10_9 1000000000 //1e9

#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll A;
ll B;
ll C;
ll N;
ll M;
ll K;

ll ltmp;
string stmp;
double dtmp;

vector<ll> prime_numbers;
void getPrimeNumbers(ll n_max){
    bool is_prime[n_max+1];
    for( int ni = 0 ; ni <=n_max ; ni++ ){
        is_prime[ni]=true;
    }
   is_prime[0]=is_prime[1]=false;
    for( int number = 2 ; number <=n_max ; number++ ){
        if(is_prime[number]){
            prime_numbers.push_back(number);
            for( int ni = number*2 ; ni <=n_max ; ni+=number ){
                is_prime[ni]=false;
            }
        }
    }
}

int main(){

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

    cin >> A;
    getPrimeNumbers(base10_5+10000);
    decltype(prime_numbers)::iterator it = lower_bound(prime_numbers.begin(), prime_numbers.end(), A);
    ll idx_lower = distance(prime_numbers.begin(), it);
    //cout << idx_lower << endl;
    cout << prime_numbers[idx_lower] << endl;

}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long

lin n;
string s[301];

bool solve(int a, int b)
{
    rep(i, n)
    {
        loop(j, i + 1, n)
        {
            if(s[(i + a) % n][(j + b) % n] != s[(j + a) % n][(i + b) % n])
                return false;
        }
    }

    return true;
}

int main(void)
{
    cin >> n;
    rep(i, n)
    {
        cin >> s[i];
    }

    int res = 0;

    rep(a, n)
    {
        if(solve(a, 0))
            res += n;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a)%MOD)+((b)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define EPS (1e-20)
#define INF 214748364700000
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using VLL = std::vector<llint>;
using MCI = std::map<char, int>;
using namespace std;


int N;
int a[300010];
int suml[300010], sumr[300010];


void makeSumL(){
	int s = 0;
	priority_queue<int, VI, greater<int>> q;
	rep(i, 0, N) q.push(a[i]), s += a[i];
	repe(i, N, 2*N){
		suml[i] = s;
		q.push(a[i]);
		s += a[i];
		s -= q.top();
		q.pop();
	}
}


void makeSumR(){
	int s = 0;
	priority_queue<int> q;
	repr(i, 3*N, 2*N) q.push(a[i]), s += a[i];
	reper(i, 2*N, N){
		sumr[i] = s;
		q.push(a[i-1]);
		s += a[i-1];
		s -= q.top();
		q.pop();
	}
}


int solve(){
	int ans = -INF;
	repe(i, N, 2*N) chmax(ans, suml[i]-sumr[i]);
	return ans;
}


signed main(){
	cin >> N;
	rep(i, 0, 3*N) cin >> a[i];

	makeSumL();
	makeSumR();

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 7796
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int n;
    cin >> n;
    if(n == 1)
        cout << "Hello World" << endl;
    else {
        int a, b;
        cin >> a >> b;
        cout << a + b;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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; }



int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(25);

  int n;
  cin >> n;
  vector<pair<int, int>> x(n);
  rep(i, n) {
    cin >> x[i].first;
    x[i].first--;
    x[i].second = i;
  }

  sort(x.begin(), x.end());
  rep(i, n - 1) {
    if (x[i].first == x[i + 1].first) {
      cout << "No\n";
      return 0;
    }
  }
  vector<int> ans(n * n, -1), cnt(n, 0);
  rep(i, n) ans[x[i].first] = x[i].second;
  int idx = 0;
  rep(i, n) {
    while (cnt[x[i].second] < x[i].second) {
      if (idx == x[i].first) {
        cout << "No\n";
        return 0;
      }
      if (ans[idx] != -1) {
        idx++;
        continue;
      }
      ans[idx] = x[i].second;
      cnt[x[i].second]++;
      idx++;
    }
  }
  cnt.assign(n, n - 1);
  idx = n * n - 1;
  repr(i, n - 1){
    while (cnt[x[i].second] > x[i].second) {
      if (idx == x[i].first) {
        cout << "No\n";
        return 0;
      }
      if (ans[idx] != -1) {
        idx--;
        continue;
      }
      ans[idx] = x[i].second;
      cnt[x[i].second]--;
      idx--;
    }
  }
  cout << "Yes\n";
  rep(i, n * n) cout << ans[i] + 1 << ' ';
  cout << '\n';
  


  




  
  return 0;
}

Measured memory_bytes: 4268