akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pi 3.1415926535
#define endl '\n'
using namespace std;
struct custom {
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
//using namespace __gnu_pbds;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll inf=1e19;
/*ll power(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=(y>>1);
    }
    return res;
}*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,i,j,k,w;
    cin>>n>>w;
    ll arr[n+1][2],dp[w+1][n+1];
    for(i=1;i<=n;i++)cin>>arr[i][0]>>arr[i][1];
    memset(dp,0,sizeof(dp));
    for(i=1;i<=w;i++)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j]=dp[i][j-1];
            if(i-arr[j][0]>=0)
                dp[i][j]=max(dp[i][j-1],dp[i-arr[j][0]][j-1]+arr[j][1]);
        }
    }
    cout<<dp[w][n]<<endl;
}


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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF 1000000007LL

#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

ll mypow(ll a, ll b) { if(b == 0) return 1; ll temp=mypow(a,b/2); temp=(temp*temp)%INF; if(b%2 == 1) temp=(a*temp)%INF; return temp; }
int mygcd(int a, int b) { if(b==0) return a; return mygcd(b,a%b); }
int cntBits(ll a) { int ret=0; while(a>0) { ret++; a/=2; } return ret; }
int main()
{
	ios::sync_with_stdio(0);
	int tt=1; 
//	cin >> tt;
	for(int tcase=1;tcase<=tt;tcase++)
	{
		int n; cin >> n;
		double t,a,x,ans;
		int index=1; cin >> t >> a;
		cin >> x; ans=t-(x*0.006);
		for(int i=2;i<=n;i++)
		{
			cin >> x;
			if(fabs(a-t+(x*0.006)) < fabs(a-ans))
			{
				ans=t-(x*0.006);
				index=i;
			}
		}
		cout << index << "\n";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
int main()
{
  string s;
  cin >> s;
  vector<char> S(s.length());
  rep(i, s.length()) S.at(i) = s.at(i);
  bool yes = true;
  rep(i,s.length()/2){
    if(s.at(i)!=s.at(s.length()-1-i))
      yes = false;
  }
  rep(i,s.length()/4){
    if(s.at(i)!=s.at(s.length()/2-1-i))
      yes = false;
  }
  for (int i = 0;i<(s.length()-(s.length()+3)/2)/2;i++){
    int l = i + (s.length() + 3) / 2-1;
    if (S.at(l) != S.at(s.length()-1 - i))
      yes=false;
  }
  puts(yes ? "Yes" : "No");
}

Measured memory_bytes: 256
y, x= map(int,input().split())
bomb = [0 for i in range(y)]
ary = [[0 for i in range(x)]for i in range(y)]

for i in range(y):
    bomb[i] = list(input())

for a in range(y):
    for b in range(x):
        if bomb[a][b] == "#":
            ary[a][b] = "#"
        else :
            ary[a][b] = 0
# この配列を用意することによって’＃’の周りの計算を楽にできるようになる
height_ary =[-1,-1,-1, 0,0, 1,1,1]
width_ary  =[-1, 0 ,1,-1,1,-1,0,1]

for a in range(y):
    for b in range(x):
        if ary[a][b] == "#":
            for i in range(8):
                h = height_ary[i] + a
                w = width_ary [i] + b
                if h < 0 or h >= y: continue
                if w < 0 or w >= x: continue
                if not ary[h][w] == "#":
                    ary[h][w] += 1

for i in range(y):
    result = map(str,ary[i])
    print("".join(result))

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

//nが固定値のとき
const int MOD = 1e9 + 7;
 
vector<long long> fact_inv, inv, Com;
 
/*  init_nCk :二項係数のための前処理
    計算量:O(k)
*/
void init_nCk(int n, int SIZE) {
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
    Com.resize(SIZE + 5);
    Com[0] = 1;
    for (int i = 1; i < SIZE + 5; i++) {
        Com[i] = Com[i - 1] * ((n - i + 1) * inv[i] % MOD) % MOD;
    }
}
 
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int k) {
    assert(!(k < 0));
    return Com[k];
}

//xのn乗
ll mod_pow(ll x, ll n) {// O(log(n))
    ll res = 1;
    while (n > 0) {//繰り返し二乗法
        if (n & 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

main(){
    ll n, a, b;
    cin>>n>>a>>b;
    init_nCk(n,200000);
    ll ans = mod_pow(2,n);
    ans--;
    ll x = nCk(a), y = nCk(b);
    ans=(ans-x)%MOD;
    ans=(ans-y)%MOD;
    if(ans >= 0)
        cout<< ans <<endl;
    else
        cout<< ans + MOD <<endl;
}


Measured memory_bytes: 7936
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    input! {
    a:isize,
    b:isize,
    c:isize,
    d:isize,
    }
    println!("{}",if a<=b {a*c}else{b*c+(a-b)*d})
}

Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define all(x) x.begin(),x.end()
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define N

int main(){
	FIO;
	ll x; cin >> x;
    ll cur = 100, ini = 100, paso = 0;
    while(cur < x){
        cur += ini*0.01;
        ini *= 1.01;
        paso++;
    }
    cout << paso << endl;
	return 0;
}

Measured memory_bytes: 3552
#include<stdio.h>
#include<iostream>
using namespace std;
int main (){
    string a,b;
    int x;
    cin >> a >>b;
    string s = a + b;
    for(int i=0; i < s.length(); i++){
        x = x * 10 + (s[i] -'0');
    }
    for(int i=1; i<1000; i++){
        if(i * i == x){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

        if(N%2 == 0){
            System.out.println(a/(double)N);
        } else{
            System.out.println((a+1)/(double)N);
        }
    }
}

Measured memory_bytes: 21972
#[macro_use]
mod utils {
    macro_rules! input {
        ($($r:tt)*) => {
            let stdin = std::io::stdin();
            let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
            let mut next = move || -> String{
                bytes
                    .by_ref()
                    .map(|r|r.unwrap() as char)
                    .skip_while(|c|c.is_whitespace())
                    .take_while(|c|!c.is_whitespace())
                    .collect()
            };
            input_inner!{next, $($r)*}
        };
    }
    macro_rules! input_inner {
        ($next:expr) => {};
        ($iter:expr, ) => {};

        ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
        ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
        ($next:expr, _ : $t:tt $($r:tt)*) => {
            let _ = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
    }
    macro_rules! read_value {
        ($next:expr, ( $($t:tt),* )) => {
            ( $(read_value!($next, $t)),* )
        };
        ($next:expr, [ $t:tt ; $len:expr ]) => {
            (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        };
        ($next:expr, chars) => {
            read_value!($next, String).chars().collect::<Vec<char>>()
        };
        ($next:expr, usize1) => {
            read_value!($next, usize) - 1
        };
        ($next:expr, $t:ty) => {
            $next().parse::<$t>().expect("Parse error")
        };
    }
}

fn main() {
    input! {
        s: chars,
    }
    if s.contains(&'A') && s.contains(&'B') {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
//#define int long long
#define rep(i, l, r) for(int i = l; i <= r; ++ i)

inline int read() 
{
	char cc = getchar(); int cn(0), flus(1);
	while(cc < '0' || cc > '9') {if(cc == '-') flus = -flus; cc = getchar();}
	while(cc >= '0' && cc <= '9') {cn = cn * 10 + cc - 48; cc = getchar();}
	return cn * flus;
}

const int MAXN = 1e5 + 10, INF = 2147483647;
const int Mod = 998244353, G = 3;

signed main()
{
	int n = read();
	if(n >= 30) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long  ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

void solve() {
	int n, m; cin >> n >> m;
	vector<int> c(n + 1);
	rep(i, m) {
		int l, r; cin >> l >> r; l--; r--;
		c[l]++; c[r + 1]--;
	}
	rep(i, n)c[i + 1] += c[i];
	int ans = 0;
	rep(i, n) {
		if (c[i] == m) {
			ans++;
		}
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 640
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
heapq.heapify(a)
num = 0
while num < m:
    maximum = -1 * heapq.heappop(a)
    maximum //= 2
    heapq.heappush(a, -maximum)
    num += 1
print(-sum(a))

Measured memory_bytes: 86488
// Problem : B - Magic 2
// Contest : AtCoder - M-SOLUTIONS Programming Contest 2020
// URL : https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define ll       long long int
#define ull      unsigned long long int
#define pb       push_back
#define vi       vector<int>
#define vb       vector<bool>
#define vll      vector<long long int>
#define pi       pair<int,int>
#define all(x)   (x).begin(), (x).end()

const int MOD = 1000000007;




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t=1;
	//cin>>t;
	
	while(t--)
	{
		ll a,b,c,k;
		cin>>a>>b>>c;
		cin>>k;
		
		ll x=k;
		
		while(x>0 && b<=a)
		{
			b=b*2;
			x--;
			if(b>a)break;
		}
		while(x>0 && c<=b)
		{
			c=c*2;
			x--;
			if(c>b)break;	
		}
		if(a<b && b<c)cout<<"Yes\n";
		else	cout<<"No\n";
	}
	
   	return 0;
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,sum=0;
    cin>>n;
    int a[2*n+1];
    for (i=1;i<=2*n;i++)
    cin>>a[i];
    sort(a+1,a+2*n+1);
    for (i=1;i<=2*n;i+=2)
    sum+=min(a[i],a[i+1]);
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
long long a[100010];
int main() {
	int k;
	cin>>k;
	for(int i =1 ;i <= k; i++){
		scanf("%lld",&a[i]);
	}
	long long small = 2, big = 2;

	for(int i = k; i >= 1; i--){
		if(small % a[i] != 0 && big % a[i] != 0 && small/a[i] == big/a[i] ){
			printf("-1\n");
			return 0;
		}
		big = big - big%a[i];
		if(small %a[i] != 0){
			small += a[i] - small % a[i];
		}

		big += a[i] - 1;

	}
	printf("%lld %lld\n",small,big);

	return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair

using namespace std;

typedef pair<int, int> P;

int main(){
	int n;
	while(cin >> n, n){
		string s;
		cin >> s;
		stack<P> st;
		rep(i, n){
			int a, b;
			cin >> a >> b;
			st.push(MP(a-1, b-1));
		}
		while(!st.empty()){
			P p = st.top();
			st.pop();
			swap(s[p.first], s[p.second]);
			int d = abs(p.first-p.second);
			s[p.first] = 'a'+(s[p.first]-'a'+d)%26;
			s[p.second] = 'a'+(s[p.second]-'a'+d)%26;
		}
		cout << s << endl;
	}

	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;

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

#ifdef LOCAL
	#define eprintf(...) printf(__VA_ARGS__)
#else
	#define eprintf(...) 1
#endif

#define ROUNDUP(a, b) 		( ((a) + ((b) - 1) ) / (b))
#define SET_ZERO(a)	 		( memset((a), 0, sizeof(a)))
#define SET_NUM_ARRAY(a,b)	( memset((a), b, sizeof(a)))
//#define int long long int //dont forget to change int to signed

int main() {
	int N;
	scanf("%d", &N);
	int max = 0, min = 1e9+1;
	for (int i = 0; i < N; i++) {
		int a;
		scanf("%d", &a);
		chmax<int>(max, a);
		chmin<int>(min, a);
	}

	printf("%d\n", max - min);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int k, s, co = 0;
  cin >> k >> s;
  for(int i = 0; i < k + 1; i++){
    for(int j = 0; j < k + 1 && i + j <= s; j++){
      if(s - i - j <= k) co++;
    }
  }
  cout << co << endl;
  return 0;
}


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

int main() {
  int n;
  
  while(cin>>n && n != -1) {
    double x = 1.0, y = 0.0, r, th = 0.0;
    for(int i = 1; i < n; i++) {
      r = sqrt(x*x+y*y);
      th += atan(1.0/r);
      r = sqrt(r*r+1.0);
      x = r*cos(th), y = r*sin(th);
    }
    printf("%.2f\n%.2f\n", x, y);
  }
  
  return 0;
}

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

using namespace std;

#define REPEAT(i, N) for (int i = 0; i < (N); i++)

int main() {
  int N, M, sum = 0;
  
  cin >> N >> M;
  
  REPEAT(i, M) {
    int _in;
    
    cin >> _in;
    
    sum += _in;
  }
  
  if (N < sum) {
    cout << -1 << endl;
  } else {
    cout << N - sum << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int ans = 0;
int work(ll k) {
  int T = 1e7 + 7;
  ll now = 7, ans = 1;
  while (T--) {
    if (now % k == 0) {
      return ans;
    }
    now = now % k;
    now = now * 10 + 7;
    ans++;
  }
  return -1;
}
int main() {
  ll k;
  while (cin >> k) {
    cout << work(k) << endl;
  }
}

Measured memory_bytes: 3592
n=input()
for i in range(n):
    if i==0:
        num_1=input()
    elif i==1:
        num_2=input()
        maxv=num_2 - num_1
        MIN=min(num_1,num_2)
    else:
        num_3=input()
        if (num_3-MIN)>maxv:
            maxv=num_3-MIN
        if (num_3)<MIN:
            MIN=num_3
print(maxv)
 

Measured memory_bytes: 12704
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b;
  cin >> a >> b;
  
  if(a<=0&&0<=b)
    cout << "Zero"<<endl;
  if(a<=b&&b<0){
    if((b-a+1)%2==1)
      cout <<"Negative"<< endl;
    if((b-a+1)%2==0)
      cout << "Positive"<<endl;
  }
  if(0<a&&a<=b)
    cout<<"Positive"<<endl;
}

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

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();

		// スペース区切りの整数の入力
		List<Long> list = new ArrayList<Long>();
		for (int i = 0; i < N * 3; i++) {
			long a = sc.nextInt();
			list.add(a);
		}

		Collections.sort(list);

		long ans = 0;
		for (int i = 0; i < N; i++) {
			ans += list.get(3 * N - 2 - i * 2);
		}
		// 出力
		System.out.println(ans);
		// System.out.println("Hello");
	}
}

Measured memory_bytes: 100116
nml = input().split()
n, m, l = map(int, nml)

A = [[int(i) for i in input().split()] for j in range(n)]
B = [[int(i) for i in input().split()] for j in range(m)]

C = [[0 for i in range(l)] for j in range(n)]

for j in range(n):
    for i in range(l):
        s = 0
        for k in range(m):
            s += A[j][k]*B[k][i]
        C[j][i] = s

for i in C:
    print(' '.join(map(str, i)))

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

int main()
{
  int N;
  int a[16];
  pair<int, int> b[16][16];
  int res=0;
  cin >> N;

  rep(i,N) {
    cin >> a[i];
    rep(j, a[i]){
      int x, y;
      cin >> x >> y;
      b[i][j] = make_pair(x, y);
    }
  }

  int shojiki[16];
  rep(i, 1<<N){// for all pattern                                                        
    rep(j, N){ // create pattern                                                         
      shojiki[j] = (i&1<<j) >> j;
    }
    bool correct = true;
    rep(j, N) {// for person                                                             
        if(shojiki[j]==1){
          rep(k, a[j]){ //for testimoni                                                  
            int x = b[j][k].first;
            int y = b[j][k].second;
            if(shojiki[x-1]!=y) correct = false;
          }
        }
    }
    int total_shojiki = 0;
    rep(j,N) {
      if(shojiki[j]==1) total_shojiki++;
      //cout << shojiki[j];                                                              
    }
    //cout << endl;                                                                      
    //if(correct) cout << "correct" << endl;                                             
    //else cout << "XXX" << endl;                                                        
    //cout << "----" << endl;                                                            
    if(correct) res = max(res, total_shojiki);
  }

  cout << res << endl;
}


Measured memory_bytes: 256
import numpy as np

def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    # dp = [[0] * (S + 1) for i in range(N + 1)]
    # dp[0][0] = 1
    
    dp = np.zeros(S + 1, np.int64)
    dp[0] = 1
    
    for i, a in enumerate(A, start=1):
        # i - 1 番目までの数で 合計が X になる組み合わせが
        # dp[i-1][X] 個あるのであれば、
        # そのdp[i-1][X] 個 のそれぞれに対してAi を加える/加えないの
        # 2パターンが考えられるので、dp[i-1]を2倍する
        dp_next = 2 * dp
        
        # さらに、i - 1 番目までの数で 合計が X - Ai になる組み合わせが
        # dp[i-1][X - Ai] 個ある場合、
        # i番目の数(Ai)を足すことで合計をXにできる
        dp_next[a:] += dp[:-a] # dp[:-a] = dp[:len(dp)-a]       

        # 大きくなりすぎないように逐次MODをとる
        dp_next %= MOD
        
        dp = dp_next

    # print(*dp, sep='\n')
    print(dp[S])

if __name__ == '__main__':
    main()

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

int main() 
{
  int n;
  cin >> n;
  int a[n], b[n], c[n-1];
  int p = 0;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i], p+=b[i];
  for (int i = 0; i < n-1; i++) cin >> c[i];
  for (int i = 0; i < n-1; i++) {
    if (a[i+1] == a[i]+1) p+=c[a[i]-1];
  }
  
  cout << p;
  return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
//#define all(x) (x).begin(),(x).end()
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;

signed main(){
    int x,a,b;
    cin >>x >> a >> b;
    if(abs(x - a) > abs(x - b)) cout << 'B' << '\n';
    else cout << 'A' << '\n';
    return 0;   
}


Measured memory_bytes: 256
N = int(input())
S = input()

# Z-algorithm (A[i] = (Longest Common Profix of S and S[i:]))
# demonstrate in the case S = 'aaabaaab'
def LCP(S, N):
    A = [N] + [0] * (N - 1)
    max_length = 0
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        A[i] = j
        max_length = min(max(max_length, j), i)
        if j == 0:
            i += 1
            continue
        else:
            k = 1
            while i + k < N and k + A[k] < j:
                A[i + k] = A[k]
                max_length = min(max(max_length, A[k]), i + k)
                k += 1
            i += k
            j -= k
    return max_length

ans = 0
for i in range(N):
    cand = LCP(S[i:], N - i)
    ans = max(ans, cand)

print(ans)

Measured memory_bytes: 52828
/*
 * src.cpp
 *
 *  Created on: 2016/08/04
 *      Author: joi
 */

#include <bits/stdc++.h>

using namespace std;

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

const double EPS=1e-10;

#define EQ(a,b) fabs(a-b)<EPS

double r;
double bin[12]={128,64,32,16,8,4,2,1,0.5,0.25,0.125,0.0625};

int out[12];

int main(){
	do{
		cin>>r;
		if (r>=0-EPS){
			fill(out,out+12,0);
			REP(i,12){
				if (r>=bin[i]-EPS){
					r-=bin[i];
					out[i]=1;
				}
			}
			if (EQ(r,0)){
				REP(i,8){
					cout<<out[i];
				}
				cout<<'.';
				REP(i,4){
					cout<<out[i+8];
				}
				cout<<endl;
			}else{
				cout<<"NA"<<endl;
			}
		}
	}while (r>=0-EPS);
	return 0;
}

Measured memory_bytes: 1228
def BubleSort(N, data):
    flag = 1
    cnt = 0
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if data[i] < data[i-1]:
                data[i], data[i-1] = data[i-1], data[i]
                flag = 1
                cnt = cnt + 1
    return data, cnt

N = int(input())
data = [ int(i) for i in input().split()]

new_data, cnt = BubleSort(N, data)

for n in range(N):
    if n:
        print(" ", end="")
    print(data[n], end="")
print()
print(cnt)


Measured memory_bytes: 5632
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define show(x) cout<<#x<<"="<<x<<"\n"
using namespace std;

int n,m;
string s;
map<int,int> mp;

int main(){
 ios::sync_with_stdio(false);
 cin.tie(0);
 cout.precision(10);
 cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in", "r", stdin); 
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
 cin>>n;
 for(int i=0;i<n;i++){
  int a;cin>>a;
  mp[a]++;
 }
 ll ans=0;
 for(auto ite=mp.begin();ite!=mp.end();ite++){
  int a=ite->fi;
  int b=ite->se;
  if(a>b){
   ans+=b;
  }else if(a<b){
   ans+=b-a;
  }
 }
 cout<<ans<<endl;
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
 return 0;
}

Measured memory_bytes: 4736
#include "bits/stdc++.h"
using namespace std;
#define fastcin {\
    cin.tie(0);\
    ios::sync_with_stdio(false);\
}
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = a; i >= b; i--)
#define fore(i, a) for(auto &i:a)
#define print(x) cout << x << "\n"
#define SORT(a, n) sort(a, a+n);
#define REVERSE(a,n) reverse(a,a+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VREVERSE(v) reverse(v.begin(), v.end());
#define MOD 1000000007
#define yes "YES"
#define no "NO"
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;

int main() {
    fastcin;
    int n, m;
    cin >> n;
    string s = to_string(n);
    m = 0;
    rep(i, 0, s.size()) {
        m += s[i]-'0';
    }
    if(n%m!=0) s = "No";
    else s = "Yes";
    print(s);
    return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
H = list(map(int,input().split()))
good = [1 for i in range(N)]

for i in range(M):
  a,b = map(int,input().split())
  if(H[a-1] < H[b-1]):
    good[a-1] = 0
  elif(H[a-1] == H[b-1]):
    good[a-1] = 0
    good[b-1] = 0
  else:
    good[b-1] = 0
    
ans = sum(good)
print(ans)

Measured memory_bytes: 20124
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define int long long

signed main(){
    // cout << fixed << setprecision(10) << flush;

    string s;
    cin >> s;
    if(s[s.size()-1] == 's') s += "es";
    else s += 's';
    cout << s << endl;

    return 0;
}

Measured memory_bytes: 3624
N,M,X = map(int,input().split())
a=list(map(int,input().split()))

sum=len(a)
cost=100
costL=0
for i in range(M):
  if a[i]!=0 and a[i]<X:
    costL=costL+1
if min(costL,sum-costL)<cost:
  cost=min(costL,sum-costL)
print(cost)


Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second

int main(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    cout << A + B + C - max(A, max(B, C)) + max(A, max(B, C)) * pow(2, K) << endl;
}


Measured memory_bytes: 4108
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
// AUTHOR:: MOHAMMAD FAISAL
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,r;
    cin >> n >> r;
    if(n>=10)
        cout<<r<<endl;
    else
        {
            int temp = 100*(10-n);
            cout<<(r+temp)<<endl;
        }
        return 0;
}

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

typedef long long ll;
int main()
{
  ll n;
  cin>>n;
  ll a[n];
  ll cnt=0;
  for(ll i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]==0)
      cnt++;
  }
  //cout<<cnt<<endl;
  if(cnt>0)
    cout<<0;
  else
  {
    ll ans=1;
    // cout<<"";
    for(ll i=0;i<n;i++)
    {
      ll result=ans*a[i];
      cout<<"";
      if((result/a[i])!=ans)
      {
        // cout<<"negative"<<endl;
        cout<<-1;
        return 0;
      }
      ans=result;
      //cout<<ans<<endl;
    }
    if(ans>1000000000000000000)
      cout<<-1;
    else
      cout<<ans;
  }
  return 0;
}
  


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

int main() {
  ll a,b; cin >>a>>b;
  cout << max({a+b,a-b,a*b}) << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = INT_MAX;
const ll LINF = LLONG_MAX;
const ll MOD = 1e9+7;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"[";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"]";return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&p)
{o<<"{"<<p.first<<", "<<p.second<<"}";return o;}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj)
{o<<"{";for(auto itr=obj.begin();itr!=obj.end();++itr)o<<(itr!=obj.begin()?", ":"")<<*itr;o<<"}";return o;}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s,t;
  cin >> s >> t;
  vector<vector<int>> pos(26);
  ll ss = s.size(), ts = t.size();

  for(int i=0; i<ss; i++){
    pos[s[i]-'a'].push_back(i);
  }
  ll ans = -1;
  for(int i=0; i<ts; i++){
    int c = t[i]-'a';
    ll next, cur = ans % ss;
    if(pos[c].empty()){
      cout << -1 << endl;
      return 0;
    }
    auto it = upper_bound(pos[c].begin(), pos[c].end(), cur);
    if(it == pos[c].end()){
      next = (ans/ss + 1) * ss + pos[c][0];
    }else{
      next = (ans/ss) * ss + (*it);
    }
    ans = next;
  }
  cout << ans+1 << endl;

  return 0;
}


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


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

    string O,E;
    cin >> O >> E;
    int x=O.size()+E.size();
    string A="";
    rep(i,x){
        int d=i/2;
        if(i%2==0) A+=O.at(d);
        else A+=E.at(d);
    }
    cout << A << endl;



}

Measured memory_bytes: 256
buff = "NNNNWNNNWNNNENNNENNNWNNN"

class Dice:
        num =[ -1 for x in range(6) ]
        def roll(self, d):
                if   d == "N":
                        b = self.num[0]
                        self.num[0] = self.num[1]
                        self.num[1] = self.num[5]
                        self.num[5] = self.num[4]
                        self.num[4] = b
                elif d == "S":
                        b = self.num[0]
                        self.num[0] = self.num[4]
                        self.num[4] = self.num[5]
                        self.num[5] = self.num[1]
                        self.num[1] = b
                elif d == "W":
                        b = self.num[3]
                        self.num[3] = self.num[0]
                        self.num[0] = self.num[2]
                        self.num[2] = self.num[5]
                        self.num[5] = b
                elif d == "E":
                        b = self.num[3]
                        self.num[3] = self.num[5]
                        self.num[5] = self.num[2]
                        self.num[2] = self.num[0]
                        self.num[0] = b
        
        def __init__(self, lst):
                self.num = lst
        
        def print_num(self, m):
                #print(self.num[m])
                return self.num[m]
        
        def return_lst(self):
                return self.num

def isSameDice(D1, D2):
        for d in buff:
                D1.roll(d)
                if D1.return_lst() == D2.return_lst():
                        return True
        return False

N = int(input())
dices = []

for n in range(N):
        lst = [ int(i) for i in input().split() ]
        dices.append(Dice(lst))

for i in range(N):
        for j in range(i + 1, N):
                if isSameDice(dices[i], dices[j]):
                        print("No")
                        exit()

print("Yes")


Measured memory_bytes: 5616
import java.util.Scanner;

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

		String s = sc.next();

		if(s.equals("ABC")) {
			System.out.println("ARC");
		}else {
			System.out.println("ABC");
		}

		sc.close();
	}
}


Measured memory_bytes: 26888
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

int main(){
   int n,m,x;
   cin >> n >> m >> x;

   int g[n][m+1],a[m];
   rep(i,n){
      cin >> g[i][0];
      rep(k,m) cin >> g[i][k+1];
   }
  
   ll MIN = 1000000000;
   for(int i=0;i<(1<<n);i++){
      rep(i,m) a[i] = 0;//初期化
      ll sum =0;
      for(int k=0;k<n;k++){
         if(i&(1<<k)){
            rep(i,m) a[i]+= g[k][i+1];
            sum += g[k][0];
         }
      }
      bool j=true;
      rep(i,m) if(a[i]<x) j = false;

      if(j) MIN = min(MIN,sum); 
   }
   if(MIN != 1000000000)cout << MIN << endl;
   else cout << -1 << endl;
   return 0;
}


Measured memory_bytes: 3632
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    maps=[]
    n = int(input())
    maps=[list(map(int,input().split())) for _ in range(2)]
    dp=[]
    for i in range(n):
        total=sum(maps[0][:i+1])+sum(maps[1][i:])
        dp.append(total)
    print(max(dp))

if __name__=="__main__":
    main()

Measured memory_bytes: 9080
/*
    Written by Nitrogens
    Desire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

const int maxn = 1e3+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;

#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl

char maze[maxn][maxn];
ll dp[maxn][maxn];

int main()
{
    //ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);

    int h, w;
    scanf("%d%d", &h, &w);

    for(int i = 1; i <= h; i++)
    {
        scanf("%s", maze[i] + 1);
    }

    dp[1][1] = 1;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * (maze[i - 1][j] == '.')) % Mod;
            dp[i][j] = (dp[i][j] + dp[i][j - 1] * (maze[i][j - 1] == '.')) % Mod;
            //dp[i][j] = (dp[i][j] + maze[i][j] == '.') % Mod;
        }
    }
    printf("%lld\n", dp[h][w] % Mod);

    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}


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

#ifdef SG
        #include <debug.h>
#else
        #define show(...)
        #define debug(...)
        #define deepen(...)
        #define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef int64_t ll;
typedef uint64_t ull;
typedef uint32_t ui;
typedef uint16_t us;
typedef uint8_t uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

struct Input {

    int n, k;
    ve< vi > g;

        bool read () {
        if (scanf("%d%d", &n, &k) != 2) return 0;
        g.assign(n, vi());
        forn (i, n - 1) {
            int u, v;
            scanf("%d%d", &u, &v);
            --u, --v;
            g[u].pb(v);
            g[v].pb(u);
        }
                return 1;
        }

        void init (const Input &input) {
                *this = input;
        }
};

struct Data: Input {

    int ans;

        void write () {
                printf("%d\n", ans);
        }
};

struct Solution: Data {

    vi used;

    int dfs(int x, int dist) {
        used[x] = 1;
        int res = 1;
        for (int to : g[x]) {
            if (dist && !used[to]) {
                res += dfs(to, dist - 1);
            }
        }
        return res;
    }

        void solve () {
        ans = n;
        if (k % 2 == 0) {
            forn (v, n) {
                used.assign(n, 0);
                umn(ans, n - dfs(v, k / 2));
            }
        } else {
            forn (v, n) {
                for (int to : g[v]) {
                    if (to > v) {
                        used.assign(n, 0);
                        used[v] = used[to] = 1;
                        umn(ans, n - dfs(v, k / 2) - dfs(to, k / 2));
                    }
                }
            }
        }
        }

        void clear () {
                *this = Solution();
        }
};

Solution sol;

int main () {
        cout.setf(ios::showpoint | ios::fixed);
        cout.precision(20);
#ifdef SG
        while (sol.read()) {
                sol.solve();
                sol.write();
                sol.clear();
        }
#else
        sol.read();
        sol.solve();
        sol.write();
#endif
        return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pye cout << "yes" << endl;
#define pno cout << "no" << endl;
#define pYe cout << "Yes" << endl;
#define pNo cout << "No" << endl;
#define pYE cout << "YES" << endl;
#define pNO cout << "NO" << endl;
#define prin(num) cout << num << endl;
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000
#define MOD 1000000007LL
#define MAX 100005
#define NIL -1
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> doup;
typedef map<ll, ll> Map;

int main(void) {
    string s;
    ll a=0, b=0, c=0, d=0, i;
    cin >> s;
    for(i=0; i<s.size(); i++) {
        if(s[i]=='N') a=1;
        else if(s[i]=='S') b=1;
        else if(s[i]=='W') c=1;
        else d=1;
    }
    
    if(a==b && c==d) pYe
    else pNo
    
}


Measured memory_bytes: 256
r,g,b,n=map(int,input().split())
m=[r,g,b]
m.sort(reverse=1)
r,g,b=m[0],m[1],m[2]
ans=0
if m==[1,1,1]:
  print((n+2)*(n+1)//2)
else:
  for i in range(n+1):
    if r*i>n:
      break
    for j in range(n+1):
      if r*i+g*j>n:
        break
      if (n-r*i-g*j)%b==0:
        ans+=1
  print(ans)

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

int main(void){
    int n;
    cin >> n;
    vector<int> vec(n);
    int ans;

    for(int i=0; i<n; i++){
        cin >> vec.at(i);
    }

    sort(vec.begin(), vec.end());

    double maxd = vec.at(n-1);
    for(int i=0; i<n-1; i++){
        double diff = abs((double)vec.at(n-1)/2 - vec.at(i));
        if(diff < maxd){
            maxd = diff;
            ans = vec.at(i);
        }
    }

    cout << vec.at(n-1) << " " << ans << endl;

    return 0;
}


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

int main(){
    ll n, m; cin >> n >> m;
    ll s = sqrt(m) + 1;
    ll ans = 1;
    for(int i = 1; i <= s; i++){
        if(m % i  == 0 && m /i >= n){
            ans = max((ll)i, ans);
        }
        if(m % i == 0 && i >= n){
            ans = max((ll)m/i, ans);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
int p[210000];
int in[210000];
vector<int>v[210000];
int num[210000];
vector<int>g[210000];
int main(){

	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)num[i]=-1;
	for(int i=0;i<a;i++){
		scanf("%d",p+i);p[i]--;
		in[p[i]]++;
		g[p[i]].push_back(i);
	}
	queue<int>Q;
	for(int i=0;i<a;i++){
		if(in[i]==0){
			Q.push(i);
		}
	}
	while(Q.size()){
		int at=Q.front();Q.pop();
		std::sort(v[at].begin(),v[at].end());
		int cur=0;
		for(int i=0;i<v[at].size();i++){
			if(cur<v[at][i]){
				break;
			}else if(cur==v[at][i]){
				cur++;
			}
		}
		num[at]=cur;
		v[p[at]].push_back(num[at]);
		in[p[at]]--;
		if(in[p[at]]==0){
			Q.push(p[at]);
		}
	}
	for(int i=0;i<a;i++){
		if(num[i]==-1){
			std::sort(v[i].begin(),v[i].end());
			int cur=0;
			vector<int>f;
			for(int j=0;j<v[i].size();j++){
				if(cur<v[i][j]){
					f.push_back(cur);
					if(f.size()==2)break;
					cur++;
					if(cur==v[i][j])cur++;
				}else if(cur==v[i][j]){
					cur++;
				}
			}
			while(f.size()<2){
				f.push_back(cur);cur++;
			}
			bool ok=false;
			for(int j=0;j<2;j++){
				int at=p[i];
				int nx=f[j];
				while(1){
					std::sort(v[at].begin(),v[at].end());
					int cur=0;
					for(int k=0;k<v[at].size();k++){
						if(nx==cur)cur++;
						if(cur<v[at][k]){
							break;
						}else if(cur==v[at][k]){
							cur++;
						}
					}
					if(nx==cur)cur++;
					nx=cur;
			//		printf("%d: %d %d\n",at,f[j],cur);
					if(at==i){
						if(nx==f[j])ok=true;
						break;
					}
					at=p[at];
				}
				if(ok)break;
			}
			if(!ok){
				printf("IMPOSSIBLE\n");
			}else printf("POSSIBLE\n");
			return 0;
		}
	}
}

Measured memory_bytes: 18688
#include <bits/stdc++.h>
using namespace std;
#define int long long

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

  vector<int> plus, minus;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if(a >= 0) plus.push_back(a);
    else minus.push_back(a);
  }
  sort(plus.rbegin(), plus.rend());
  sort(minus.begin(), minus.end());

  if(plus.empty()) {
    plus.push_back(minus.back());
    minus.pop_back();
  }
  if(minus.empty()) {
    minus.push_back(plus.back());
    plus.pop_back();
  }

  vector<pair<int,int>> ans;
  for (int i = 1; i < plus.size(); i++) {
    ans.emplace_back(minus[0], plus[i]);
    minus[0] -= plus[i];
  }
  ans.emplace_back(plus[0], minus[0]);
  plus[0] -= minus[0];
  for (int i = 1; i < minus.size(); i++) {
    ans.emplace_back(plus[0], minus[i]);
    plus[0] -= minus[i];
  }
  cout << plus[0] << endl;
  for (auto it : ans) cout << it.first << " " << it.second << endl;
}

Measured memory_bytes: 5104
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
    static void Main()
    {
        SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().Solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";


    void Solve()
    {
        var x = cin.Nextlong;
        long sum = 2 * (x / 11);
        if (0 < x % 11)
        {
            sum++;
        }
        if (6 < x % 11)
        {
            sum++;
        }
        WriteLine(sum);
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] Scan { get { return ReadLine().Split(); } }
    public int[] Scanint { get { return Array.ConvertAll(Scan, int.Parse); } }
    public long[] Scanlong { get { return Array.ConvertAll(Scan, long.Parse); } }
    public double[] Scandouble { get { return Array.ConvertAll(Scan, double.Parse); } }
    public string Next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return Next;
        }
    }
    public int Nextint { get { return int.Parse(Next); } }
    public long Nextlong { get { return long.Parse(Next); } }
    public double Nextdouble { get { return double.Parse(Next); } }
}

Measured memory_bytes: 2648
#include <iostream>
#include<algorithm>
using namespace std;
static const int MAX =2000000;

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

int maxv=-2000000000;
int minv= R[0];
for(int i =1;i<n;i++){
maxv =max(maxv,R[i]-minv);
minv=min(minv,R[i]);
}

cout << maxv << endl;
return 0;
}

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

void main_()
{
    ll H, W;
    vector<string> Ss;
    cin >> H >> W;
    copy_n(istream_iterator<string>(cin), H, back_inserter(Ss));

    vector<pair<int, int>> dirs = {
        { -1, -1 },
        { 0, -1 },
        { 1, -1 },
        { -1, 0 },
        { 1, 0 },
        { -1, 1 },
        { 0, 1 },
        { 1, 1 },
    };

    for (int i = 0; i < W; ++i) {
        for (int j = 0; j < H; ++j) {
            if (Ss[j][i] == '.') {
                int mines = count_if(begin(dirs), end(dirs),
                    [i, j, W, H, &Ss](auto&& p) {
                        int x = i + p.first;
                        int y = j + p.second;
                        return (0 <= x && x < W && 0 <= y && y < H && Ss[y][x] == '#');
                    });
                Ss[j][i] = mines + '0';
            }
        }
    }

    for (auto&& s : Ss) {
        cout << s << endl;
    }
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 256