akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp makepair
#define deb(x) cout<<x<<"\n";
#define deB(x,y) cout<<x<<" "<<y<<"\n";
#define Deb(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n" 
#define YES cout<<"YES\n";
#define Yes cout<<"Yes\n";
#define NO cout<<"NO\n";
#define No cout<<"No\n";
#define all(v) (v).begin(),(v).end()
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  string s;
  cin>>s;
  ll i=0,ans=0,j,val;
  ll dp[2020]={},a[2020]={};
  while(i<s.size())
  {
  	a[s[i]-'0']=1;
  	j=0;
  	while(j<2019)
  	{
  		val=((j*10)+s[i]-'0')%2019;
  		a[val]+=dp[j];
  		j++;
  	}
  	ans+=a[0];
  	j=0;
  	while(j<2019)
  	{
  		dp[j]=a[j];
  		a[j]=0;
  		j++;
  	}
  	i++;
  }
  deb(ans);
}

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

using namespace std;

char s[20];
int x,hoge;

int main() {
    cin >> s;

    if (s[0] != 'A') {
        cout << "WA\n";
        return 0;
    }
    if(s[1] == 'C' || s[1] < 95) {
        cout << "WA\n";
        return 0;
    }
    if (s[strlen(s)-1] < 95) {
        cout << "WA\n";
        return 0;
    }
    for (x=2 ; x <strlen(s)-1 ; x++) {
        if (s[x] == 'C') {
            if (hoge != 0) {
                cout << "WA\n";
                return 0;
            }
            hoge++;
        }
        if (s[x] < 60) {
            cout << "WA\n";
            return 0;
        }
    }
    if (hoge == 0) {
        cout << "WA\n";
        return 0;
    }
    cout << "AC\n";

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,k,s=0;cin>>a>>b>>c>>k;
  if(a>=k)s=k;
  else if(a+b>=k)s=a;
  else s=a-(k-a-b);
  cout<<s<<endl;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n, m;
  cin >> n >> m;
  priority_queue<long long> item;
  for(int i = 0, temp; i < n; ++i){
    cin >> temp;
    item.push(temp);
  }
  while(m--){
    long long exp = item.top(); item.pop();
    exp /= 2;
    item.push(exp);
  }
  long long sum = 0;
  for(int i = 0; i < n; ++i){
    sum += item.top();
    item.pop();
  }
  cout << sum << endl;
}

Measured memory_bytes: 1400
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 M = sc.nextInt();
      int[] a = new int[A];
      int[] b = new int[B];
      int amin = 100000;
      int bmin = 100000;
      for(int i=0;i<A;i++){
        a[i] = sc.nextInt();
        amin = Math.min(amin,a[i]);
      }
      for(int i=0;i<B;i++){
        b[i] = sc.nextInt();
        bmin = Math.min(bmin,b[i]);
      }
      //割引なし
      int ans = amin+bmin;
      //割引あり
      for(int i=0;i<M;i++){
        int cost = a[sc.nextInt()-1]+b[sc.nextInt()-1]-sc.nextInt();
        ans = Math.min(ans,cost);
      }
       System.out.println(ans);
    }
}

Measured memory_bytes: 60636
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int l[8][8];
int n,m,i,j,k,c;
void dfs(int s,int d,int M[]){
  int L[8],x;
  for(x=0;x<n;x++)L[x]=M[x];
  for(x=0;x<n;x++){
    if(L[x]&&l[s][x]){
      if(d!=n-1){L[x]=0;dfs(x,d+1,L);L[x]=1;}
      else c++;
    }
  }
}
int main(){
  int M[8];
  scanf("%d%d",&n,&m);
  for(i=0;i<n;i++)for(j=0;j<n;j++){M[i]=1;l[i][j]=0;}
  M[0]=0;
  for(i=0;i<m;i++){scanf("%d%d",&j,&k);l[j-1][k-1]=l[k-1][j-1]=1;}
  dfs(0,1,M);
  printf("%d",c);
}


Measured memory_bytes: 128
# https://atcoder.jp/contests/abc160/tasks/abc160_c

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

max_distance = -1
for i in range(len(A)):
    if len(A) - 1 == i:
        max_distance = max(max_distance, (K - A[i]) + A[0])
    else:
        max_distance = max(max_distance, A[i + 1] - A[i])

print(K - max_distance)


Measured memory_bytes: 26420
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)
n = gets.to_i
arr = []
n.times do
  arr << gets.to_i
end

arr.each do |v|
  (0..2).to_a.each do |i|
    a[i] = nil if a[i] == v
    b[i] = nil if b[i] == v
    c[i] = nil if c[i] == v
  end
end


tate1 = [a[0],b[0],c[0]].count{|n| n == nil}
tate2 = [a[1],b[1],c[1]].count{|n| n == nil}
tate3 = [a[2],b[2],c[2]].count{|n| n == nil}

yoko1 = [a[0],a[1],a[2]].count{|n| n == nil}
yoko2 = [b[0],b[1],b[2]].count{|n| n == nil}
yoko3 = [c[0],c[1],c[2]].count{|n| n == nil}

naname1 = [a[0],b[1],c[2]].count{|n| n == nil}
naname2 = [a[2],b[1],c[0]].count{|n| n == nil}

if tate1 ==3 || tate2 ==3 || tate3 ==3 || yoko1 ==3 || yoko2 ==3 || yoko3 ==3 || naname1==3 || naname2 ==3
  puts "Yes"
else
  puts "No"
end


Measured memory_bytes: 1788
#import<cstdio>
int main(){
	int a,i,n,c[]={0,1,5,10,50,100,500};
	for(;a=0,scanf("%d",&n),n;printf("%d\n",a)){
		for(n=1000-n,i=6;i;i--){
			for(;n>=c[i];a++){
				n-=c[i];
			}
		}
	}
}

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

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

int N;
int B[100];
vector<int> v;

int main(){
    cin >> N;
    for(int i=0;i<N;i++) cin >> B[i];
    for(int i=0;i<N;i++){
        int p = -1;
        int z = N-i;
        for(int j=N-1;j>=0;j--){
            if(B[j] == -1) continue;
            if(B[j] != z){
                z--;
                continue;
            }
            p = j;
            break;
        }
        if(p==-1){
            cout << -1 << endl;
            return 0;
        }
        v.push_back(B[p]);
        B[p] = -1;
    }
    reverse(v.begin(),v.end());
    for(auto &e : v) cout << e << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

typedef long long ll;


int main()
{
	long long N;
	scanf("%lld", &N);
	int i = 1;
	ll a = 2;
	ll b = 1;
	ll ans = 2;
	if (N == 1)
	{
		printf("%lld",b);
		return 0;
	}
	while (i < N)
	{
		ans = a + b;
		a = b;
		b = ans;
		i++;
	}
	printf ("%lld\n",ans);
	return (0);
}

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

int main() {

int a1,a2,a3;

cin>>a1>>a2>>a3;

if(a1<=a2 && a1<=a3){
	if(a2<=a3) cout<<(a2-a1)+(a3-a2)<<endl;
	else if(a2>a3) cout<<(a3-a1)+(a2-a3)<<endl;
}
else if(a1>=a2 && a2<=a3){
	if(a1<=a3) cout<<(a1-a2)+(a3-a1)<<endl;
	else if(a1>a3) cout<<(a3-a2)+(a1-a3)<<endl;
}
else if(a1>=a3 && a2>=a3){
	if(a1<=a2) cout<<(a1-a3)+(a2-a1)<<endl;
	else if(a1>a2) cout<<(a2-a3)+(a1-a2)<<endl;
}


	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 3e3 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
 
ld dp[N][N];

signed main() {
	IOS;
	#ifdef LOCAL
		freopen("input.txt","r", stdin);
		freopen("output.txt","w",stdout);
	#endif
	int n;	cin >> n;
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		ld p;
		cin >> p;
		dp[i][0] = dp[i-1][0]*(1-p);
		for(int j = 1; j <= n; j++)
			dp[i][j] = dp[i-1][j]*(1-p) + dp[i-1][j-1]*p;
	}	
	ld ans = 0;
	for(int i = n/2+1; i <= n; i++)
		ans += dp[n][i];
	cout << setprecision(10) << fixed << ans;
	return 0;
}

Measured memory_bytes: 141056
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define mp make_pair
typedef long long int ll;
typedef unsigned long long int ull;
#define fi first
#define se second
#define pb push_back
ll p=pow(10,9)+7;
int q=998244353;
typedef long double ld;
const double PI =  3.141592653589793238;
 
ll power(ll x, ll y, ll pp)
{
    ll res = 1;
    x = x % pp;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % pp;
        y = y>>1;
        x = (x*x) % pp;
    }
    return res;
}
 
ll modInverse(ll n, ll pp)
{
    return power(n, pp-2, pp);
}
ll factorial(ll n) 
{ 
    // single line to find factorial 
    
ll ans = 1;
for (int i=1;i<=n;i++)
{
    ans = ans*i;
}
return ans;
} 
bool isPrime(int n) 
{ 
    // Corner case 
    if (n <= 1)  return false; 
  
    // Check from 2 to n-1 
    for (int i=2; i<n; i++) 
        if (n%i == 0) 
            return false; 
  
    return true; 
} 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   ll n;
  cin>>n;
  ll arr[n];
  for(int i=0;i<n;i++)
    cin>>arr[i];
  ll sum=0;
  for(int i=1;i<n;i++)
  {
    if(arr[i] < arr[i-1])
    {
      sum=sum+(arr[i-1]-arr[i]);
      arr[i]=arr[i-1];
    }
  }
  cout<<sum;
    return 0;
}







Measured memory_bytes: 5212
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,n) for (int i=(n-1);i >= 0;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)((v).size())
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))
using namespace std; using ll = long long; using P = pair<int,int>;
using vl = vector<ll>; using vvl = vector<vl>;
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << H << " ";
    debug_out(T...);
}
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
    for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
    return os;
}
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
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;}
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const int dx[8] = {1,0,-1,0,1,1,-1,-1}; const int dy[8] = {0,1,0,-1,1,1,-1,-1};

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    // kは要素数
    int k = pow(2*n,0.5);
    if(k*(k+1) != 2*n){
        cout << "No" << endl;
        return 0;
    }else{
        cout << "Yes" << endl;
        cout << k+1 << endl;
        vvl ans(k+1,vl(k));
        ans[0][0] = 1;
        int v = 2;
        rep(i,1,k){
            ans[0][i] = ans[0][i-1] + v;
            v++;
        }
        rep(i,1,k+1){
            bool flag = false;
            int a = 0;
            int b = i;
            rep(j,k){
                if(j == 0){
                    ans[i][0] = 1 + (i-1)*i/2;
                    a = ans[i][0];
                    continue;
                }
                if(a == ans[0][i-1]) flag = true;
                if(flag){
                    ans[i][j] = ans[i][j-1]+b;
                    b++;
                    continue;
                }
                ans[i][j] = ans[i][j-1]+1;
                a++;
            }
        }
        rep(i,k+1)
            cout << k << " " << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 2944
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
int main() {
	int n, p, r, k, t, s, d, v;
	cin >> n;
	int m[100][100] = {};
	rep(i,n) {
		cin >> r >> k;
		rep(j,k) {
			cin >> t;
			m[r-1][t-1] = 1;
		}
	}
	int ret[100][100] = {};
	rep(i,100) {
		ret[i][i] = 1;
	}
	rep(i,n) {
		queue<int> q;
		q.push(i);
		while(!q.empty()) {
			int a = q.front(); q.pop();
			rep(j,n) {
				if(m[a][j] && ret[i][j]==0) {
					q.push(j);
					ret[i][j] = ret[i][a]+1;
				}
			}
		}
	}
	cin >> p;
	rep(i,p) {
		cin >> s >> d >> v;
		--s,--d;
		if(ret[s][d] > v || ret[s][d] == 0) cout<< "NA" << endl;
		else cout << ret[s][d] << endl;
	}
	return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    ll res = 0;
    string s;
    cin >> s;
    ll dp[s.size() + 1][4] = {0};
    dp[0][0] = 1;
    rep (i, s.size()) {
        if (s[i] != '?') {
            rep (j, 4) {
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][j] %= MOD;
            }
        } else {
            rep (j, 4) {
                dp[i + 1][j] += dp[i][j] * 3;
                dp[i + 1][j] %= MOD;
            }
        }
        if (s[i] == 'A' || s[i] == '?') dp[i + 1][1] += dp[i][0];
        if (s[i] == 'B' || s[i] == '?') dp[i + 1][2] += dp[i][1];
        if (s[i] == 'C' || s[i] == '?') dp[i + 1][3] += dp[i][2];
        rep (j, 4) dp[i + 1][j] %= MOD;
    }
    cout << dp[s.size()][3] << endl;
    
    return 0;
}



Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;
const int MAXM=105;
const int MOD=1e9+7;
int dp[MAXN][MAXM];
int num[MAXN],d;
char s[MAXN];
int main() {
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;++i){
		num[i]=s[i]-'0';
	}
	cin>>d;
	dp[0][0]=1;
	for(int i=0;i<=n;++i){
		for(int j=0;j<d;++j){
			for(int k=0;k<10;++k){
				(dp[i+1][(j+k)%d]+=dp[i][j])%=MOD;
			}
		}
	}
	int ans(0);
	int sum(0);
	for(int i=1;i<=n;++i){
		for(int z=0;z<num[i];++z){
			(ans+=dp[n-i][(d+d-sum-z)%d])%=MOD;
		}
		(sum+=num[i])%=d;
	}
	ans+=(!sum);
	(ans+=MOD-1)%=MOD;
	cout<<ans<<endl;
	return 0;
}

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

int main(){
	int n;
	string s;

	cin >> n >> s;

	if(n%2 ==1){
		cout << "No"<< endl;
		return 0;
	}

	rep(i,n/2){
		if(s[i] == s[i+n/2]){
			continue;
		}else{
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	return 0;
}

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

// count how many '1' is in the vector
int num(vector<vector<int>> v) {
  int sum = 0;
  for(int i = 0; i < v.size(); i++) {
    for(int j = 0; j < v.at(0).size(); j++) {
      if(v.at(i).at(j) == 1) 
        sum++;
    }
  }
  return sum;
}

// change the numbers in a certain line of the vector into '2'
void change(int i, vector<vector<int>> &v) {
  if(i < v.size()) {
    for(int j = 0; j < v.at(0).size(); j++) {
      v.at(i).at(j) = 2;
    }
  }
  else {
    for(int j = 0; j < v.size(); j++) {
      v.at(j).at(i-v.size()) = 2;
    }
  }
  return;
}

// check the answer
int answer_check(int x, int k, vector<vector<int>> v) {
  vector<vector<int>> vcopy = v;
  int a = num(vcopy);
  if(a < k)
    return 0;
  
  else {
    int s = 0;
    if(a == k)
      s++;
    int sum = 0;
    for(int i = x; i < vcopy.size() + vcopy.at(0).size(); i++) {
      change(i,vcopy);
      sum += answer_check(i+1,k,vcopy);
      vcopy = v;
    }
    return sum + s;
  }
}
      
int main() {
  int H,W,K;
  cin >> H >> W >> K;
  vector<vector<int>> vec(H, vector<int>(W,0));
  for(int i = 0; i < H; i++) {
    string s;
    cin >> s;
    for(int j = 0; j < W; j++) {
      if(s.at(j) == '#')
        vec.at(i).at(j) = 1;
    }
  }
  int ans = answer_check(0, K, vec);
  cout << ans << endl;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int dp[N],n;
vector<int>v;
int main()
{
	cin>>n;
	for(int i=0;i<=1e5;i++)dp[i]=1e9;
	v.push_back(1);
	for(int i=6;i<=1e5;i*=6)v.push_back(i);
	for(int i=9;i<=1e5;i*=9)v.push_back(i);
	dp[n]=0;
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<v.size();j++)
		{
			if(v[j]>i)continue;
			dp[i-v[j]]=min(dp[i-v[j]],dp[i]+1);
		}
	}
	cout<<dp[0]<<endl;
	return 0;
}

Measured memory_bytes: 640
use std::io;
use std::str::FromStr;

fn input_tuple() -> (i64, i64, i64, i64) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<i64> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1], vec[2], vec[3])
}


fn main() {
    let (x1, y1, x2, y2) = input_tuple();
    println!("{} {} {} {}", x2 - (y2 - y1), y2 + (x2 - x1), x1 - (y2 - y1), y1 + (x2 - x1));
}


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

int main()
{
    int N, tmp;
    cin >> N >> tmp;
    set<int> a;
    a.insert(tmp);

    string result="YES";
    for(int i=1; i<N; i++)
    {
        cin >> tmp;
        if(a.count(tmp))
        {
            result = "NO";
            break;
        }
        a.insert(tmp);
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 9600
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b){return *(char*)a - *(char*)b;} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b){return strcmp(*(const char **)a, *(const char **)b);} /* aaa,aab.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007

typedef long long int lli;

int main(void) {
  int h ,w;
  scanf("%d %d", &h, &w);
  char s[51][51];
  rep(i, 0, h) {
    scanf("%s", s[i]);
  }

  int mx[4] = {0, 1, 0, -1};
  int my[4] = {1, 0, -1, 0};
  int ok = 1;
  rep(hi, 0 ,h) {
    rep(wi, 0, w) {
      if (s[hi][wi] == '.') continue;
      int no = 1;
      rep(mi, 0, 4) {
        if (s[hi + my[mi]][wi + mx[mi]] == '.') continue; 
        no = 0; break;
      }
      if (no) { printf("No\n"); return 0; }
    }
  }
  printf("Yes\n");
  return 0;
}


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

	long long sum=0;
	for(int i=1;i<=n;i++){
		if (!(i%3)||!(i%5)){
			continue;
		}
		sum+=i;
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    char now = s[0];
    int ans = 0;
    for(int i=1;i<s.length();i++){
        if(s[i] != now){
            now = s[i];
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
import math
from functools import reduce
aaa = int(input())
baa = list(map(int, input().split()))


def gcd (a,b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)
res = baa[0]
for c in baa[1::]:
    res = gcd(res , c)
print(res)




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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ld eps = 1e-9;
const ll MOD = 998244353;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

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

  int n; cin >> n;
  vll a(n);
  ll ma = 0;
  ll su = 0;
  for(int i=0;i<n;++i) {
    cin >> a[i];
    ma = max(ma, a[i]);
    su += a[i];
  }

  vvll dp(n+1, vll(n*ma+1, 0));
  dp[0][0] = 1;
  for(int i=0;i<n;++i) {
    for(int j=0;j<=n*ma;++j) {
      dp[i+1][j] += 2*dp[i][j] % MOD;
      dp[i+1][j] %= MOD;
      if(j + a[i] <= n*ma) {
        dp[i+1][j+a[i]] += dp[i][j];
        dp[i+1][j+a[i]] %= MOD;
      }
    }
  }

  ll su2 = su / 2 + su % 2;
  ll cnt1 = 0;
  for(int i=su2;i<=ma*n;++i) {
    cnt1 += dp[n][i];
    cnt1 %= MOD;
  }
  cnt1 *= 3;
  cnt1 %= MOD;

  vvll dp2(n+1, vll(n*ma+1, 0));
  dp2[0][0] = 1;
  for(int i=0;i<n;++i) {
    for(int j=0;j<=n*ma;++j) {
      dp2[i+1][j] += dp2[i][j];
      dp2[i+1][j] %= MOD;
      if(j + a[i] <= n * ma) {
        dp2[i+1][j+a[i]] += dp2[i][j];
        dp2[i+1][j+a[i]] %= MOD;
      }
    }
  }

  ll cnt2 = (su % 2 ? 0 : 3 * dp2[n][su/2] % MOD);
  //cout << cnt1 << ":" << cnt2 << endl;

  ll po3 = 1;
  for(int i=0;i<n;++i) {
    po3 *= 3;
    po3 %= MOD;
  }
  //cout << po3 << endl;
  cout << (po3 + (MOD - cnt1) + cnt2) % MOD << endl;

}


Measured memory_bytes: 424512
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text.RegularExpressions;
using System.Text;
using System.Diagnostics;
using static System.Math;
using static System.Array;

//var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
namespace AtCoderSolve
{

    class Solve
    {
        const int mod = 1000000007;
        const int INF = 2147483647;
        const long SINF = 9223372036854775807;

        static int N, A;
        static int[] x;
        
        

        public static void Input()
        {
            var cin = new Scanner();
            var input = cin.SplitReader();
            N = input[0];
            A = input[1];
            x = cin.SplitReader();
        }

        static void Main(string[] args)
        {
            Input();

            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);

            long[,,] dp = new long[N + 1, N + 1, 50 * N + 1];

            
            for(var i = 0; i <= N; i++)
            {
                for(var j = 0; j <= i; j++)
                {
                    for(var s = 0; s <= 50 * N; s++)
                    {
                        if (i == 0) { dp[i, j, s] = s == 0 ? 1 : 0; }
                        else if (j == 0)
                        {
                            dp[i, j, s] = s == 0 ? 1 : 0;
                        }
                        else
                        {
                            if (s - x[i - 1] < 0)
                            {
                                dp[i, j, s] = dp[i - 1, j, s];
                            }
                            else
                            {
                                dp[i, j, s] = dp[i - 1, j - 1, s - x[i - 1]] + dp[i - 1, j, s];
                            }
                        }
                    }
                    
                }
            }

            long ans = 0;
            for(var i = 1; i <= N; i++)
            {
                ans += dp[N, i, A * i];
            }

            Console.WriteLine(ans);

            //Console.Out.Flush();

        }





    }

    public class Scanner
    {
        public int[] SplitReader()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReaderL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }

    }

    public class Graph
    {
        
    }
}

    



Measured memory_bytes: 61536
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))
tofh = [(t - x * 0.006) for x in h]
import math
deltaoft = [math.fabs(tofx - a) for tofx in tofh]
print(deltaoft.index(min(deltaoft)) + 1)

Measured memory_bytes: 3064
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int main(){
    string s;
    cin >> s;
    if(s=="ABC"){
        cout<<"ARC"<<endl;
    }else{
        cout<<"ABC"<<endl;
    }
    return 0;
}



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

typedef long long int ll;
typedef pair<ll, ll> pii;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define sz(a) ll(a.size())
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front 
#define MAXN 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define debug(x) cout << '>' << #x << ':' << x << " ";
#define nl '\n'
#define INF 1000000000000000000
#define IO                 \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define int long long int

// const int N = 1e6;
// int dp[N][2][2];
ll modpower(ll x, ll y, ll p)
{
    ll res = 1;     // Initialize result
    x = x % p;
    if (y==0)return 1;
    if(x==0)return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; // y = y/2
        x = (x*x) % p;  // Change x to x^2
    }
    return res;
}

void solve(){
    int n;
    cin >> n;
    if(n == 1){
        cout << 0 << nl;
        return;
    }
    int ans = 0;
    ans += modpower(10, n, MOD);
    ans += modpower(8, n, MOD);
    // ans += 
    ans %= MOD;
    ans -= modpower(9, n, MOD);
    ans += MOD;
    ans %= MOD;
    ans -= modpower(9, n, MOD);
    ans += MOD;
    ans %= MOD;
    // (ans *= modpower(10, n-2, MOD))%=MOD;
    cout << ans%MOD << nl;
    // cout << dp[n][1][1] << nl;
}
main()
{
    IO;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int T = 1;
    // cin >> T;
    fo(c, 1, T){
        solve();
        // cout<<"Case #"<<c<<": ";
    }
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 1e9

using namespace std;

typedef int long long ll;
typedef int long l;
typedef pair<int, int> Pii;
const ll MOD = 1000000007;

int n;
string s;

ll d[10000];

ll pow2(int x){
    if(x==0){
        return d[0]=1;
    }
    if(d[x]==0){
        return d[x]=pow2(x-1)*2;
    }
    return d[x];
}

ll solve(int m){
    ll ans=0;
    if(s.empty())return 0;
    for (int i = 1; i <= n-m; i++){
        string ts = s.substr(m,i);
        ll ti = atoll(ts.c_str());
        int flag = n-m-i-1>=0?n-m-i-1:0;
        ans+=ti*pow2(flag);
        ans+=solve(m+i);
        // cout<<m<<' '<<(ts)<<' '<<ans-ti<<' '<<flag<<endl;
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>s;
    n =s.size();
    cout << solve(0) << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
const ll INF = 1e9 + 7;
typedef pair<int,int> P;// pair型は２つの値の組を表せる

int main(){
    int N,M; cin >> N >> M;
    vector <P> p(M);
    rep(i,M) cin >> p[i].first >> p[i].second;
    
    rep(i,1000){
        string S=to_string(i);
        int keta=S.length();
        
        if(keta!=N) continue;
        bool ans=true;
        rep(i,M){
            if (S[p[i].first-1] != p[i].second +'0') ans=false;
        }
        
        if (ans){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
void print(ll x){
	if(x<0)putchar('-'),x=-x;
	int y=x%10+'0';
	if(x>=10)print(x/10);
	putchar(y);
}
string s,t,ans;
int dp[3005][3005];
int main(){
	cin >> s >> t;
	for(int i=0;i<=s.size();i++)
		for(int j=0;j<=t.size();j++){
			if(i==0 or j==0)dp[i][j]=0;
			else if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	int i=s.size(),j=t.size();
	while(i and j){
		if(s[i-1]==t[j-1])
			i--,j--,ans+=s[i];
		else if(dp[i-1][j]>dp[i][j-1])i--;
		else j--;
	}
	for(int i=ans.size()-1;i>=0;i--)
		putchar(ans[i]);
	return 0;
}

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


int main() {
    int N,T;
    cin >> N >> T;
    vector<pair<int,int>> H(N);
    rep(i,N) {
        cin >> H[i].first >> H[i].second;
    }
    int tle = 0;
    int costmin = 100000;
    rep(j,N) {
        if (H[j].second <= T ) {
            tle++;
            if (H[j].first < costmin) {
                costmin = H[j].first;
            }
        }
    }
    if (tle == 0) {
        cout << "TLE" << endl;
    }
    else {
        cout << costmin << endl;
    }
}



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

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];
	ll sum = 0;
	rep(i, n) sum += b[i];
	vector<ll> res(n);
	rep(i, n) res[i] = a[i] + b[i];
	sort(res.rbegin(), res.rend());
	ll ans = 0;
	rep(i, n) {
		if (i % 2 == 0)ans += res[i];
	}
	ans -= sum;
	cout << ans << endl;
	return 0;
}


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

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

pair<string,int> dic[1010];

int main(void){
	int n=0;
	while(true){
		string key;
		int num;
		cin >> key >> num;
		if(cin.eof())
			break;
		dic[n].first=key;
		dic[n++].second=num;
	}
	sort(dic,dic+n);
	string prev="";
	rep(i,n){
		if(prev==""){
			cout << dic[i].first << endl;
			cout << dic[i].second;
		}else if(prev==dic[i].first){
			cout << " " << dic[i].second;
		}else{
			cout << endl;
			cout << dic[i].first << endl;
			cout << dic[i].second;
		}
		prev=dic[i].first;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1248
#include <stdio.h>
int main(){
    int a,b,c;
    int cnt = 0;
    scanf( "%d %d %d", &a, &b, &c );
    for( ; a <= b ; a++ ){
        if( c % a == 0 ){
            cnt++;
        }
    }
    printf("%d\n" , cnt );
}


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

int main(){
string S , T;
  cin >> S >> T ;
  
 for (int i = 0; i < T.size() - 1 ; i++){
   
   if (S[i] != T[i]){
     cout << "No" << endl ;
     return 0;
   }
   
 }     
   
  cout <<"Yes"<< endl ;
}

Measured memory_bytes: 3552
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int n, k, x, y;
  cin >> n >> k >> x >> y;

  int sum;
  if (n > k) {
    sum = x * k + y * (n - k);
  } else {
    sum = x * n;
  }

  cout << sum << endl;
  return 0;
}

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

#define ED return 0;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) long(pow(x,y))
const long long int mod = 1000000007;
unsigned long long int gcd(unsigned long long int a, unsigned long long int b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

void ipowmod(long long int i,long long int total){
    if(i == 0){
        cout << total << endl;
        exit;
    }
    else{
        i--;
        total *= 2;
        if(total >= mod){
            total -= mod;
        }
        ipowmod(i,total);
    }
}

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

    long long int N;
    cin >> N;
    vector<long long int> vec (N);
    for(long long int i = 0;i < N;i++){
        cin >> vec.at(i);
    }
    SORT(vec)
    if(N % 2 == 0){
        for(long long int i = 0;i < N / 2;i++){
            if(vec.at(i*2) != i*2+1 || vec.at(i*2+1) != i*2+1){
                cout << 0 << endl;
                ED
            }
        }
    }
    else{
        if(vec.at(0) != 0){
            cout << 0 << endl;
            ED
        }
        for(long long int i = 0;i < N / 2;i++){
            if(vec.at(i*2+1) != i*2+2 || vec.at(i*2+2) != i*2+2){
                cout << 0 << endl;
                ED
            }
        }
    }
   ipowmod(N/2,1);
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <set>
#include <queue>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb(x) push_back(x)
typedef long long LL;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
int cnt[N],vis[N],a[N];
int main()
{
    int n,x;
    while(~scanf("%d",&n))
    {
        mem(cnt,0);
        mem(vis,0);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        int tmp=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==i)
            {
                tmp++;
                if(i==n)
                    swap(a[i],a[i-1]);
                else swap(a[i],a[i+1]);
            }
        }
        printf("%d\n",tmp);
    }
    return 0;
}

/*
9
1 2 4 9 5 8 7 3 6
5
1 4 3 5 2
8
1 2 4 3 5 6 8 7
*/


Measured memory_bytes: 1408
#include <cstdio>
int max(int a, int b) {return a > b ? a : b;}
int main()
{
    int n, h, t = 0, ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &h);
        if (h >= t) {++ans; t = h;}
    }
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 128
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format, std.datetime;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] lreads(T = long)(long n){return generate(()=>readln.chomp.to!T()).take(n).array();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
// dfmt on

void main()
{
    long N = lread();
    long k = 1;
    while (k * (k - 1) / 2 < N)
        k++;
    if (k * (k - 1) / 2 != N)
    {
        writeln("No");
        return;
    }
    writeln("Yes");
    writeln(k);
    foreach (i; 0 .. k - 1)
    {
        auto ans = new long[](k);
        ans[0] = k - 1;
        foreach (j; 0 .. i)
        {
            long base = (i) * (i + 1) / 2;
            ans[j + 1] = base + j + 1;
        }
        foreach (j; 0 .. k - i - 1)
        {
            long base = (j + i) * (j + i + 1) / 2 + 1;
            ans[i + j + 1] = base + i;
        }
        ans.to!(string[]).join(' ').writeln();
    }
    auto ans = new long[](k);
    ans[0] = k - 1;
    foreach (i; 0 .. k - 1)
    {
        ans[i + 1] = (i + 1) * (i + 2) / 2;
    }
    ans.to!(string[]).join(' ').writeln();
}


Measured memory_bytes: 6140
#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    multiset<ll, greater<ll>> s;
    for(ll i = 0; i < (1 << n); ++i){
        ll si;
        cin >> si;
        s.insert(si);
    }

    multiset<ll> s2;
    s2.insert(*s.begin());
    s.erase(s.begin());
    while(!s.empty()){
        multiset<ll> s3;
        for(auto it = s2.begin(); it != s2.end(); ++it){
            auto it2 = s.upper_bound(*it);
            if(it2 == s.end()){
                cout << "No" << endl;
                return 0;
            }else{
                s3.insert(*it2);
                s.erase(it2);
            }
        }
        s2.insert(s3.begin(), s3.end());
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 18688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
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; }

const int MOD = 1000000007;
const int INF = 1e9;

const int mod = 1000000007;
const int inf = 1e9;
#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int k;
    cin >> k;
    queue<ll> q;
    for(int i = 1; i < 10; i++) q.push(i);
    for(int i = 0; i < k-1; i++) {
        ll cur = q.front();
        q.pop();
        int m = cur%10;

        if(m != 0) q.push(cur*10+m-1);
        q.push(cur*10+m);
        if(m != 9) q.push(cur*10+m+1);
    }
    ll ans = q.front();
    cout << ans << endl;
}

Measured memory_bytes: 5116
//
//  main.cpp
//  cf
//
//  Created by Dong Truong on 6/3/19.
//  Copyright © 2019 Dong Truong. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;
#define maxn 1000001

int cmod=1e9+7;
int n,a[maxn],m,f[maxn];

void nhap()
{
    cin>>n>>m;
    for (int i=1;i<=m;++i) cin>>a[i];
    f[1]=1;f[0]=1;
    int o=1;
    a[m+1]=1e9;
    if (a[1]==1)
    {
        f[1]=-1;++o;
    }
    for (int i=2;i<=n;++i)
        if (i==a[o])
        {
            ++o;f[i]=-1;
        }
        else
        {
            if (f[i-2]!=-1) f[i]+=f[i-2];
            if (f[i-1]!=-1) f[i]=(f[i]+f[i-1])%cmod;
            if (f[i]==0) f[i]=-1;
        }
    if (f[n]==-1) cout<<0;
    else
    cout<<f[n];
}
int main(int argc, const char * argv[]) {
    //freopen("a.inp","r",stdin);
    nhap();
    return 0;
}


Measured memory_bytes: 4736
import sys
sys.setrecursionlimit(50000)

def dfs(friends, friend, cluster, visited, belongs, index):
    for i in friends[friend]:
        if not visited[i]:
            visited[i] = True
            cluster.add(i)
            belongs[i] = index
            dfs(friends, i, cluster, visited, belongs, index)

def make_clusters(friends, N):
    clusters = []
    visited = [False] * N
    belongs = [0] * N
    index = 0
    for i in range(N):
        if not visited[i]:
            cluster = set()
            visited[i] = True
            belongs[i] = index
            cluster.add(i)
            dfs(friends, i, cluster, visited, belongs, index)
            index += 1
            clusters.append(cluster)
    return (clusters, belongs)
    
    
N, M, K = map(int, input().split())

friends = [[] for _ in range(N)]
blocks = [set() for _ in range(N)]
clusters = []

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    friends[A].append(B)
    friends[B].append(A)

for _ in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    blocks[C].add(D)
    blocks[D].add(C)

clusters, belongs = make_clusters(friends, N)

clusters_len = len(clusters)
cluster_len = [0] * clusters_len
for i in range(clusters_len):
    cluster_len[i] = len(clusters[i])

for i in range(N):
    ans = cluster_len[belongs[i]] - len(friends[i]) - len(clusters[belongs[i]] & blocks[i]) - 1
    print(ans, end=' ')

print()


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

#define rep(i,n)  for(int i = 0; i < (int)(n); i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

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

constexpr int K = 62;
constexpr int mod = 1e9+7;
ll dp[K+1][3];

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll N; std::cin >> N;
  rep(i,60) rep(j,2) dp[i][j] = 0;
  dp[K][0] = 1;
  // Condition :
  //  a + b <= N
  for(int i=K; i>=1; i--) {
    int n = (N>>(i-1))%2;
    // j := N>>i - v>>i
    // k : (a,b) = (0,0), (0,1), (1,1) de 0, 1, 2
    rep(j,3) rep(k,3) {
      int s = 2*j+n-k;
      if ( s < 0 ) continue;
      if ( s >= 2 ) s = 2;
      dp[i-1][s] += dp[i][j];
      dp[i-1][s] %= mod;
    }
  }
  std::cout << (dp[0][0] + dp[0][1] + dp[0][2])%mod << std::endl;
  return 0;
}



Measured memory_bytes: 3612
/* template.cpp [[[ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)s)
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)s)
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* ]]] */

ll n, t, q;
ll a[100000], d[100000]; 
ll x[100000];
ll s[100000];
ll p[100000];

int main(){
  cin >> n >> t >> q;
  rep(i, n) cin >> a[i] >> d[i];
  rep(i, q) cin >> x[i];

  int ii = -1;
  rep(i, n){
    if (d[i] == 1) ii = i;
    else s[i] = ii;
  }
  
  ii = -1;
  rrep(i, n){
    if (d[i] == 2) ii = i;
    else s[i] = ii;
  }

  rep(i, n){
    if (d[i] == 1){
      if (s[i] == -1) p[i] = a[i] + t;
      else p[i] = min(a[i] + t, (a[s[i]] + a[s[s[i]]]) / 2);
    }
    if (d[i] == 2){
      if (s[i] == -1) p[i] = a[i] - t;
      else p[i] = max(a[i] - t, (a[s[i]] + a[s[s[i]]]) / 2);
    }
  }

  rep(i, q) cout << p[x[i] - 1] << endl;
}

Measured memory_bytes: 6236
# -*- coding: utf-8 -*-
N = int(input())
W = list(map(int, input().split()))

TOTAL = sum(W)
S2 = 0
ans = []
for T in range(N):
    S1 = 0
    for i in range(T):
        S1 += W[i]
    S2 = TOTAL - S1
    ans.append(abs(S1 - S2))
print(min(ans))


Measured memory_bytes: 3060
def main():
    n = int(input())
    num = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if x == y:
            num += 1
            if num >= 3:
                print("Yes")
                return
        else:
            num = 0
    print("No")

if __name__ == "__main__":
    main()

Measured memory_bytes: 9176
package main

import (
    "fmt"
)

const mod = 1e9 + 7

func main() {
    var h, w int
    fmt.Scan(&h, &w)

    ms := make([][]byte, h)
    for i := range ms {
        var bs []byte
        fmt.Scan(&bs)
        ms[i] = bs
    }

    // dp[i][j] i,jの行き方
    dp := make([][]int, h)
    for i := range dp {
        dp[i] = make([]int, w)
    }

    dp[0][0] = 1
    for i := range dp {
        for j := range dp[i] {
            if i >= 1 && ms[i-1][j] == '.' {
                dp[i][j] += dp[i-1][j]
            }
            if j >= 1 && ms[i][j-1] == '.' {
                dp[i][j] += dp[i][j-1]
            }
            dp[i][j] %= mod
        }
    }

    fmt.Println(dp[h-1][w-1])
}


Measured memory_bytes: 11008
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		var W = GetStrings(N);
		var set = new HashSet<string>();
		set.Add(W[0]);
		for(long i = 1; i < N; i++)
		{
			if(set.Contains(W[i]))
			{
				WriteLine("No");
				return;
			}
			set.Add(W[i]);
			
			if(W[i].First() != W[i - 1].Last())
			{
				WriteLine("No");
				return;
			}
		}
		WriteLine("Yes");
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 28332