akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {

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

  int x;

  cin >> x;

  int st = 600;

  for(int i = 8; i >= 1; i--) {
    if(x < st) {
      cout << i;
      return 0;
    }
    st += 200;
  }

  return 0;
}
/*

*/


Measured memory_bytes: 3652
class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self, n0, n1, n2, n3, n4, n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5

    def roll(self, loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3], self.work[1], self.work[0], self.work[5], self.work[4], self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1], self.work[5], self.work[2], self.work[3], self.work[0], self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4], self.work[0], self.work[2], self.work[3], self.work[5], self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2], self.work[1], self.work[5], self.work[0], self.work[4], self.work[3])

    def equals(self, another):

        ret = False;

        for i in range(len(self.order)):
            self.roll(self.order[i])
            FLG = True
            for k in range(6):
                if self.number[k] != another.number[k]:
                    FLG = False
                    break
            if FLG == True:
                return True

        return ret


num_dice = int(input())
DICE = []

for i in range(num_dice):
    table = list(map(int, input().split()))
    tmp_dice = Dice()
    tmp_dice.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])
    DICE.append(tmp_dice)

FLG = True

for i in range(num_dice - 1):
    for k in range(i + 1, num_dice):
        if DICE[i].equals(DICE[k]) == True:
            FLG = False
            break

if FLG == True:
    print("Yes")
else:
    print("No")



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

int main() {
    int N;
    cin >> N;
    vector<int> P(N), Q(N), R(N);
    for (int i = 0; i < N; i++)
    {
        cin >> P[i];
    }
    for (int i = 0; i < N; i++)
    {
        cin >> Q[i];
    }
    
    iota(R.begin(), R.end(), 1);

    int a = 0, b = 0;
    int num = 0;
    do
    {   
        if (a != 0 && b != 0)
        {
            break;
        }
        
        num++;
        if (R[0] == P[0])
        {
            bool flgP = true;
            for (int i = 1; i < N; i++)
            {
                if (R[i] != P[i])
                {
                    flgP = false;
                    break;
                }                
            }
            if (flgP)
            {
                a = num;
            }            
        }
        if (R[0] == Q[0])
        {
            bool flgQ = true;
            for (int i = 1; i < N; i++)
            {
                if (R[i] != Q[i])
                {
                    flgQ = false;
                    break;
                }                
            }
            if (flgQ)
            {
                b = num;
            }            
        }    
    } while (next_permutation(R.begin(), R.end()));
    
    cout << abs(a - b) << endl;
  return 0;
}


Measured memory_bytes: 256
N, T = map(int, input().split())
xs = list(map(int, input().split()))

m = 10**10
M = 0
ans = 1
for x in xs:
    if x < m:
        m = x
    elif x - m == M:
        ans += 1
    elif x - m > M:
        ans = 1
        M = x - m

print(ans)

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

int main(){
    int a,b;
    cin>>a>>b;
    cout<<a*                                                                                                                                                                                                                                                                                                                                                                                                                                                         b<<" "<<2*(a+b)<<endl;
    return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> T(N);
    for (int i = 0; i < N; i++)
    {
        cin >> T[i];
    }
    int M;
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        pair<int, int> p;
        cin >> p.first >> p.second;
        int total = 0;
        for (int j = 0; j < N; j++)
        {
            if ((p.first - 1) == j)
            {
                total += p.second;
            }
            else
            {
                total += T[j];
            }
        }
        cout << total << endl;
    }

    return 0;
}

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

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

inline void Main() {
  // code
  string s;
  cin >> s;
  if(s == "SUN") cout << 7 << endl;
  if(s == "MON") cout << 6 << endl;
  if(s == "TUE") cout << 5 << endl;
  if(s == "WED") cout << 4 << endl;
  if(s == "THU") cout << 3 << endl;
  if(s == "FRI") cout << 2 << endl;
  if(s == "SAT") cout << 1 << endl;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

vector<vector<int>> v;
vector<int> p,m,M,ans;
bool f=0;

void dfs(int i=0,int q=-1){
    if(i!=0&&p[i]!=-10000000&&p[q]!=-10000000&&abs(p[i]-p[q])>1) f=1;
    if(p[i]!=-10000000){
        m[i]=p[i];M[i]=p[i];
        for(auto j:v[i]) if(j!=q) dfs(j,i);
        return;
    }
    if(v[i].empty()) return;
    for(auto j:v[i]){if(j!=q){
        dfs(j,i);
        m[i]=max(m[i],m[j]-1);
        M[i]=min(M[i],M[j]+1);
    }}
    if(m[i]>M[i]) f=1;
}

void dfs2(int i=0,int q=-1){
    if(i==0) ans[i]=m[i];
    for(auto j:v[i]){if(j!=q){
        if(m[j]==-10000000) ans[j]=ans[i]-1;
        else{
            for(int k=-1;k<=1;++k){
                if(m[j]<=ans[i]+k&&ans[i]+k<=M[j]){
                    ans[j]=ans[i]+k;
                    break;
                }
            }
        }
        dfs2(j,i);
    }}
}

void dfs3(int i=0,int q=-1){
    if(i>0&&abs(ans[i]-ans[q])!=1) f=1;
    if(p[i]!=-10000000&&p[i]!=ans[i]) f=1;
    for(auto j:v[i]) if(j!=q) dfs3(j,i);
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k,a,b,g,q;
    cin>>n;
    v.resize(n);
    fr(i,n-1){
        cin>>a>>b;
        v[--a].emplace_back(--b);
        v[b].emplace_back(a);
    }
    cin>>k;
    p.resize(n,-10000000);
    m.resize(n,-10000000);
    M.resize(n,10000000);
    fr(i,k){
        cin>>g>>q;
        p[--g]=q;
    }
    dfs();
    if(f){
        cout<<"No"<<endl;
        return 0;
    }
    ans.resize(n);
    ans[0]=m[0];
    dfs2();
    dfs3();
    if(f){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    fr(i,n){
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#include <unistd.h>
#include <random>

using namespace std;
typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#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) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

long long int factorial(long long int a){
    long long int ans = 1;
    for(int i = 0;i < a;i++){
        ans *= i+1;
    }
    return ans;
}

int main(){
//    random_device rnd;
//    mt19937 mt(rnd());
      cin.tie(0);
      ios::sync_with_stdio(false);
      long long int r, D, first;
      cin >> r >> D >> first;
      for(long long int i = 0;i < 10;i++){
          first = first * r - D;
          cout << first << endl;
      }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define reep(i,n) for(ll i = n; i >-1; i--)
#define deb(variable) cout<<#variable<<"="<<variable<<endl
#define MMOD(i) ((i%MOD)+MOD)%MOD;
#define vec(i,j) vector<vector<ll>>(i,vector<ll>(j,0))
const ll INF=99999999999999999;
const ll MOD=128;
const ll MAX_N=500010;
ll a,b,c,d,e,x,y,z,k,m,n,l,q,ans=0;
vl v(100010,0),anss(100010,0);
vp p[100010];
string s;
void dfs(ll s,ll t){
    v[s]=1;
    if(t%2==0)anss[s]=0;
    else anss[s]=1;
    rep(i,p[s].size()){
        a=p[s][i].first;
        b=p[s][i].second;
        if(v[a]==0)dfs(a,t+b);
    }
}
ll solve(void){
    dfs(1,0);
 
    rep(i,n){
        cout<<anss[i+1]<<endl;
    }
 
    return 0;
}
int main(){
    cin>>n;
    rep(i,n-1){
        cin>>a>>b>>c;
        p[a].emplace_back(b,c);
        p[b].emplace_back(a,c);
    }
 
    solve();
}

Measured memory_bytes: 11008
#include <bits/stdc++.h>
#define mp make_pair
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 1LL << 30;
const ll LINF = 1LL << 60;
const double eps = 1e-9;
const ll MOD = 1000000007LL;
int main() {
    int n,q;cin>>n>>q;
    string s;cin>>s;
    vector<int> co(n+10);
    for(int i=1;i<n;i++){
        co[i]+=co[i-1];
        if(s[i]=='C'&&s[i-1]=='A'){
            co[i]++;
        }
    }
    while(q--){
        int l,r;cin>>l>>r;--l;--r;
        cout<<co[r]-co[l]<<endl;
    }
}


Measured memory_bytes: 1408
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {

        InputStreamReader is = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(is);

        List<String> mylist = new ArrayList<>();

        // 標準入力からの値を変数strinputに代入
        String strinput = reader.readLine();

        while (strinput != null) {

            mylist.add(strinput);
            strinput = reader.readLine();

        }

        String s = mylist.get(0);

        if (s.substring(2, 3).equals(s.substring(3, 4))
                && s.substring(4, 5).equals(s.substring(5, 6))) {
            System.out.println("Yes");
        } else {
            System.out.println("No");

        }

    }

}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 1000010
#define rep(i, n) for(int i = 0; i < (n); ++i)
const ll mod = 1e9 + 7;

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

bool pairCompare(const P &firstElof, const P &secondElof) {
    return firstElof.second < secondElof.second;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int m = max(a, max(b, c));
    bool flag = false;
    if(m == a) {
        if(a == b + c) {
            flag = true;
        }
    } else if(m == b) {
        if(b == a + c) {
            flag = true;
        }
    } else {
        if(c == a + b) {
            flag = true;
        }
    }

    if(flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define MAXN 2 * 100005
long long n, A[MAXN], a[MAXN], ans, b;
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> A[i];
        a[i] = 1;
        if(A[i] - A[i - 1] > 1){
            b = -1;
        }
        else if(A[i] == A[i - 1]){
            a[i] = a[i - 1] + 1;
        }
        if(A[i] > i){
            b = -1;
        }
    }
    if(b == -1){
        cout << b << endl;
        return 0;
    }
    for(int i = 0; i < n; i++){
        if(i == n - 1){
            ans += A[i] * a[i];
        }
        else{
            if(a[i] > a[i + 1]){
                if(A[i] < A[i + 1]){
                    ans += A[i] * (a[i] - 1);
                }
                else if(A[i] > A[i + 1]){
                    ans += A[i] * a[i];
                }
            }
            else if(a[i] == a[i + 1]){
                if(A[i] > A[i + 1]){
                    ans += A[i] * a[i];
                }
            }
        }
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 3456
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

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

	int n, a, b;
	cin >> n >> a >> b;

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

	long long fatigue = 0;
	for (int i = 0; i < n - 1; ++i) {
		if ((long long) (towns[i + 1] - towns[i]) * a < b) {
			fatigue += (long long) (towns[i + 1] - towns[i]) * a;
		} else {
			fatigue += b;
		}
	}

	cout << fatigue << "\n";

	return 0;

}

Measured memory_bytes: 3716
program answer
  implicit none
  character(len=3) :: S
  read(*,*) S
  if(S(1:1)=='R'.and.S(2:2)=='R'.and.S(3:3)=='R') then
     write(*,*) '3'
     stop
  else if(S(1:1)=='R'.and.S(2:2)=='R'.and.S(3:3)=='S') then
     write(*,*) '2'
  else if(S(1:1)=='S'.and.S(2:2)=='R'.and.S(3:3)=='R') then
     write(*,*) '2'
  else if(S(1:1)=='S'.and.S(2:2)=='S'.and.S(3:3)=='S') then
     write(*,*) '0'
  else
     write(*,*) '1'
  end if

  stop
 end program answer

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

int main(){
  // 2~nの順列を生成すればよい.(始点が1で固定なので)

  int N,M; cin >> N >> M;

  vector<int> v(N);
  for(int i = 0;i < N;i++){
    v[i] = i + 1;
  }

  vector<pair<int,int>> e(M);
  for(int i = 0;i < M;i++){
    int a,b; cin >> a >> b;
    e[i] = make_pair(a,b);
  }


  int ans = 0;


  do{
    bool flag = true;

    for(int i = 0;i < N - 1;i++){
      int a = min(v[i],v[i+1]);
      int b = max(v[i],v[i+1]);

      if(find(e.begin(),e.end(),make_pair(a,b)) == e.end()){
        flag = false;
        break;
      }
    }

    if(flag)ans++;

  }while(next_permutation(v.begin()+1,v.end()));


  cout << ans << endl;



}


Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int N;//プレイヤーの人数
int player[201][3];//点数
int ans[200];
int used[101][3]={{0}};
int main()
{
  fill(ans,ans+200,0);
  cin>>N;
  for(int i = 0;i < N;i++){
    for(int j = 0;j<3;j++){
      cin >>player[i][j];
      used[player[i][j]][j]++;
    }
  }
  for(int i = 0;i <N;i++){
    for(int j = 0;j <3;j++){
      if(used[player[i][j]][j] <2){
	ans[i] +=player[i][j];
      }
    }
    cout <<ans[i]<<endl;
  }
  return 0;
}

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

#define endl "\n"
#define int long long
#define vec(x) vector<x>
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
#define matrix(x) vector<vector<x>>
#define all(v) v.begin(),v.end()
#define mem(a,b) memset(a, b, sizeof a)
#define setBits(n) __builtin_popcountll(n)
#define prec(n) fixed<<setprecision(n)
#define ff first
#define ss second
#define print(x) for(auto it:x) cout<<it<<" ";
#define dbg(x) cerr<<#x<<" :: "<<x<<endl;
#define dbg2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
const int INF = 1e9;
const int MOD = 1e9 + 7; 
const double pi = acos(-1);
int power(int a,int b,int m=MOD)
{int ans=1;while(b>0){if(b&1)ans=(ans*a)%m;a=(a*a)%m;b>>=1;}
return ans;}
int dir[]={-1, 0, 1, 0, -1};
int dx[]={1,1,0,-1,-1,-1, 0, 1};
int dy[]={0,1,1, 1, 0,-1,-1,-1};

const int N = 1e5+1;
int a[N],b[N],c[N];
int dp[N][4];
int n;

int helper(int i,int type)
{
	if(i<0)
	return 0;
	if(dp[i][type]!=-1)
	return dp[i][type];
	int ans;
	if(type==1)
	ans=a[i]+max(helper(i-1,2),helper(i-1,3));
	else if(type==2)
	ans=b[i]+max(helper(i-1,1),helper(i-1,3));
	else
	ans=c[i]+max(helper(i-1,1),helper(i-1,2));
	return dp[i][type]=ans;
}

void solve()
{
	int i;
	cin>>n;
	for(i=0;i<n;i++)
	cin>>a[i]>>b[i]>>c[i];
	mem(dp,-1);
	cout<<max(helper(n-1,1),max(helper(n-1,2),helper(n-1,3)))<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--)
		solve();
}

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

typedef long long ll;

const int N = 1e5 + 5;
int n;
ll ans;
int Arr[N];
int dp[2][N][2];
// L & R - index - first or second?

void calc(int d) {
	vector <int> s1, s2, add;

	for (int i = 0; i < n; i++) {
		dp[d][i][0] = dp[d][i][1] = -1;

		while (s2.size() && Arr[s2.back()] < Arr[i])
			s2.pop_back();
		if (s2.size())
			dp[d][i][1] = max(dp[d][i][1], s2.back());


		while (s1.size() && Arr[s1.back()] < Arr[i]) {
			add.push_back(s1.back());
			s1.pop_back();
		}

		while (add.size()) {
			while (s2.size() && Arr[s2.back()] < Arr[add.back()])
				s2.pop_back();

			s2.push_back(add.back());
			add.pop_back();
		}

		if (s1.size()) {
			dp[d][i][0] = s1.back();
			if (1 < s1.size())
				dp[d][i][1] = max(dp[d][i][1], s1[s1.size() - 2]);
		}
		s1.push_back(i);
	}

	s1.clear();
	s2.clear();
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &Arr[i]);

	calc(0);
	reverse(Arr, Arr + n);
	calc(1);
	reverse(Arr, Arr + n);
	for (int i = 0; i < n; i++)
		for (int id = 0; id < 2; id++)
			if (dp[1][i][id] != -1)
				dp[1][i][id] = n - 1 - dp[1][i][id];
	for (int i = 0, j = n - 1; i < j; i++, j--)
		swap(dp[1][i], dp[1][j]);

	for (int i = 0; i < n; i++) {
		ll l, r;
		if (dp[0][i][0] != -1) {
			l = dp[0][i][1] + 1;
			r = dp[1][i][0] - 1;
			if (dp[1][i][0] == -1)
				r = n - 1;

			ans += (dp[0][i][0] - l + 1) * (r - i + 1) * Arr[i];
		}
		if (dp[1][i][0] != -1) {
			l = dp[0][i][0] + 1;
			r = dp[1][i][1] - 1;
			if (dp[1][i][1] == -1)
				r = n - 1;

			ans += (i - l + 1) * (r - dp[1][i][0] + 1) * Arr[i];
		}
	}

	printf("%lld", ans);
	return 0;
}

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

int main() {

    ll N, A, B;
    cin >> N >> A >> B;

    ll C = A + B;

    cout << (N / C) * A + min(N%C, A) << endl;

    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    int N;
    cin >> N;
    vector<string> S(N);
    REP(i, N) {
        cin >> S[i];
    }
    sort(All(S));
    int M;
    cin >> M;
    vector<string> T(M);
    REP(i, M) {
        cin >> T[i];
    }
    sort(All(T));
    vector<pair<string,int>> C;
    REP(i,N){
        bool cre = true;
        REP(j,C.size()){
            if(S[i] == C[j].first){
                C[j].second ++;
                cre = false;
                break;
            }
        }
        if(cre || i==0){
            C.pb(mp(S[i],1));
        }
    }

    REP(i,C.size()){
        REP(j,M){
            if(T[j] == C[i].first){
                C[i].second --;
            }
        }
    }

    int max = 0;
    REP(i,C.size()){
        if(C[i].second > max){
            max = C[i].second ;
        }
    }
    cout << max <<"\n";
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const long Mod = 1000000007;
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl = input.ReadLine().Split(' ');
        var x = int.Parse(spl[0]);
        var a = int.Parse(spl[1]);


        return x<a ? 0 : 10;
    }
}


Measured memory_bytes: 11092
def main():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')] * (N + K)
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i + k <= N - 1:
                dp[i+k] = min(dp[i+k], dp[i] + abs(H[i+k] - H[i]))
            else:
                break

    print(dp[N-1])



if __name__ == "__main__":
    main()

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

signed main() {
  int N, M;
  cin >> N >> M;
  vector<int> s[20];
  for (int i = 0; i < M; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int tmp;
      cin >> tmp;
      tmp--;
      s[i].push_back(tmp);
    }
  }
  vector<int> p(M);
  for (int i = 0; i < M; i++) cin >> p[i];

  int ans = 0;
  for (int bit = 0; bit < (1 << N); bit++) {

    bool flag = true;
    for (int i = 0; i < M; i++) {
      int cont = 0;
      for (auto x : s[i]) {
        if ((bit >> x) & 1) {
          cont++;
        }
      }

      if (cont % 2 != p[i]) {
        flag = false;
        break;
      }
    }

    if (flag) {
      ans++;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.readLine

object Main {
  def main(args: Array[String]): Unit ={
    C.answer()
  }
}

object C{
  def answer(): Unit = {
    val a = readLine.toSeq
    val b = readLine.toSeq
    a.zip(b).foldLeft(Option((Map[Char,Char](),Map[Char,Char]())))((acc, c) => {
      acc match {
        case Some(x) => {
          if((x._1.contains(c._1) && !x._1.get(c._1).get.equals(c._2)) ||
            (x._2.contains(c._2) && !x._2.get(c._2).get.equals(c._1))) {
            None
          } else {
            val p = if(x._1.contains(c._1)) x._1 else x._1 + (c._1 -> c._2)
            val q = if(x._2.contains(c._2)) x._2 else x._2 + (c._2 -> c._1)
            Some(p,q)
          }
        }
        case None => None
      }
    }) match {
      case Some(x) => println("Yes")
      case None => println("No")
    }
  }
}

Measured memory_bytes: 52556
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {

    int N;
    cin >> N;
    vector<string> n_vec;
    map<string,int> n_map;

    for (int i = 0; i < N; i++) {
        string a;
        cin >> a ;
        n_vec.push_back(a);
    }

    int M;
    cin >> M;
    vector<string> m_vec;
    map<string,int> m_map;

    for (int i = 0; i < M; i++) {
        string a;
        cin >> a ;
        m_vec.push_back(a);
    }


    //cout << "-1" << endl;

    for (int i = 0; i < n_vec.size(); i++) {

        if (n_map.count(n_vec.at(i)) == 0){
            n_map[n_vec.at(i)] = 1;
        }
        else{
            n_map[n_vec.at(i)] = n_map[n_vec.at(i)] + 1;
        }

    }
    for (int i = 0; i < m_vec.size(); i++) {

        if (m_map.count(m_vec.at(i)) == 0){
            m_map[m_vec.at(i)] = 1;
        }
        else{
            m_map[m_vec.at(i)] = m_map[m_vec.at(i)] + 1;
        }

    }

    //cout << "--------" << endl;

    int max = 0;

    for(auto itr = n_map.begin(); itr != n_map.end(); ++itr)
    {
        //itr.operator->
        string key = itr->first;
        int value = itr->second;

        //cout << key << endl;
        //cout << value << endl;

        int mainasu = m_map[key];

        int keisan = value - mainasu;
        //cout << keisan << endl;

        if (max < keisan){
            max = keisan;
        }


    }

    cout << max << endl;
 
    
}


Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <vector>
#define REP(i, n) for(int i=0;i<n;++i)

typedef long long ll;
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    vector<int> a = {};
    int mn = 1<<29;
    int ans = 0;
    for(int i=0;i<5;++i){
        int x;
        cin >> x;
        int dif = x/10*10;
        dif += (x%10>0) ? 10 : 0;
        ans += dif;
        mn = min(mn, x-dif);
    }
    ans += mn;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
<?php
  $n = trim(fgets(STDIN));
  $p = explode(" ",trim(fgets(STDIN)));
  $point = $p[0];
  $count = 1;
  for($i=0; $i<$n; $i++){
    if($p[$i] < $point){
      $point = $p[$i];
      $count++;
    }
  }
  echo $count."\n";

Measured memory_bytes: 18932
#include<bits/stdc++.h>
using namespace std;
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,k,l,m,n,o,p,q;
    while(cin>>m>>n>>o>>p)

    {
        if(abs(m-o)<=p)
            cout<<"Yes"<<endl;
        else  if(abs(m-n)<=p&&abs(n-o)<=p)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3588
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <map>
#include <stdio.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++)
void chmin(int &a, int b) { if (a > b) a = b; }

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
unsigned long long inf = (1LL << 62);
ll MOD = (ll)pow(10.0, 9.0) + 7;
pint dx[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
char da[4] = { 'R', 'L', 'D', 'U' };
char dax[4] = { -1, 1, -1, 1 };
char dax2[4] = { 1, -1, 1, -1 };
ll min(ll a, ll b)
{

	return (a < b) ? a : b;
}
ll max(ll a, ll b) { return (a > b) ? a : b; }


vector<string> Slist;
int main() {
	string S;
	cin >> S;
	
	ll index = 0;
	

	while (index < S.size()) {
		string Aval = "";

		while (index < S.size() - 1 && S[index] == 'A' && S[index + 1] == 'A') {
			index += 1;
			Aval += "A";
		}

		if (S[index] == 'A' && S[index + 1] == 'B' && S[index + 2] == 'C') {
			index = index + 3;
			string val = "ABC";
			while (index < S.size() - 1) {
				if (index < S.size() - 1 && S[index] == 'B' && S[index + 1] == 'C') {
					index = index + 2;
					val += "BC";
				}
				else if (index < S.size() - 2 && S[index] == 'A' && S[index + 1] == 'B' & S[index + 2] == 'C') {
					val += "ABC";
					index = index + 3;
				}
				else if (index < S.size() - 1 && S[index] == 'A' && S[index + 1] == 'A') {
					index = index + 2;
					val += "AA";
				}

				else {
					break;
				}
			}

			Slist.push_back(Aval + val);
		}

		index += 1;

	}

	ll ans = 0;
	rep(i, Slist.size()) {
		ll numA = 0;
		rep(j, Slist[i].size() - 1) {
			if (Slist[i][j] == 'B' && Slist[i][j+1] == 'C') {
				ans += numA;
			}
			if (Slist[i][j] == 'A') {
				numA += 1;
			}
		}

	}

	cout << ans << endl;
	return 0;

}

Measured memory_bytes: 1156
#include "bits/stdc++.h"
#include <random>
using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef pair<lint, lint> plint; typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define endk '\n'
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 lint MOD = 1e9 + 7, INF = 1e18;
lint dx[8] = { 0, -1, 1, 0, 1, -1, 1, -1 }, dy[8] = { 1, 0, 0, -1, -1, -1, 1, 1 };

lint H, W, M, h, w;
lint cnt_H[300000], cnt_W[300000];
plint _cnt_H[300000], _cnt_W[300000];
set<plint> pos;

int main() {
	cin >> H >> W >> M;
	REP(i, M) {
		cin >> h >> w; h--; w--;
		cnt_H[h]++; cnt_W[w]++;
		pos.insert({ h, w });
	}
	lint maxv_H = 0, maxv_W = 0;
	REP(i, H) {
		_cnt_H[i] = { -cnt_H[i], i };
		chmax(maxv_H, cnt_H[i]);
	}
	REP(i, W) {
		_cnt_W[i] = { -cnt_W[i], i };
		chmax(maxv_W, cnt_W[i]);
	}
	sort(_cnt_H, _cnt_H + H);
	sort(_cnt_W, _cnt_W + W);
	lint idx_H = 0, idx_W = 0;
	lint maxv = 0;
	while (idx_H < H && -_cnt_H[idx_H].first == maxv_H) idx_H++;
	while (idx_W < W && -_cnt_W[idx_W].first == maxv_W) idx_W++;
	if (idx_H * idx_W > M) {
		cout << maxv_H + maxv_W << endk;
		return 0;
	}
	idx_H = 0, idx_W = 0;
	while (idx_H < H && -_cnt_H[idx_H].first >= maxv_H) {
		idx_W = 0;
		while (idx_W < W && -_cnt_W[idx_W].first >= maxv_W) {
			lint score = -_cnt_H[idx_H].first - _cnt_W[idx_W].first;
			if (pos.find({ _cnt_H[idx_H].second, _cnt_W[idx_W].second }) != pos.end()) score--;
			chmax(maxv, score);
			idx_W++;
		}
		idx_H++;
	}
	cout << maxv << endk;
}


Measured memory_bytes: 36436
#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++)
typedef pair<int, int>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX =510000;
int main(){
  	unsigned long long int X;
  	cin >>X;
  	ll ans=0;
  	unsigned long long int memo=100;
  	for(int i=0;i<=5000;i++){
    	memo=(memo*1.01);
      	ans++;
      	if(memo>=X)break;
    }
  	cout<<ans<<endl;
}

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

using namespace std;

int main()
{
    long long a,b;
    cin >> a >> b;

    long long r, x, tmp;
    x = a * b;

    if (a < b)
    {
        tmp = a;
        a = b;
        b = tmp;
    }

    r = a % b;
    while (r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }

    cout << x / b;
    return 0;
}

Measured memory_bytes: 256
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
string s;
int n;
int solve(string s,char c)
{
//	cerr<<s<<" "<<c<<endl;
	bool ok=1;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]!=s[0])
		{
			ok=0;
		}
	}
	if(ok)return 0;
	string ss;
	for(int i=0;i+1<s.size();i++)
	{
		if(s[i]==c||s[i+1]==c)
		{
			ss.PB(c);
		}
		else ss.PB(s[i]);
	}
	return solve(ss,c)+1;
}

int main()
{
	cin>>s;
	int ans=123123;
	for(int i='a';i<='z';i++)ans=min(ans,solve(s,i));
	cout<<ans<<endl;
	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++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define rep3(i, s, n) for (int i = s; i > (int)(n); i--)
#define all(obj) obj.begin(), obj.end()
#define db(x) cerr << #x << ":" << x << " "
#define dbl(x) cerr << #x << ":" << x << "\n"
#define dbv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << endl; }
#define YN(f) cout << (f ? "YES" : "NO") << endl
#define Yn(f) cout << (f ? "Yes" : "No") << endl
#define yn(f) cout << (f ? "yes" : "no") << endl
/*
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
*/

int main() {
	int N; cin >> N;
	vector<int> p(N); rep(i, N) cin >> p.at(i);
	// vector<int> q = p;
	// dbv(p); dbv(q);
	int ans = 0;
	// int ansR = 0;
	rep(i, N - 1) {
		if (p.at(i) == i + 1) {
			swap(p.at(i), p.at(i + 1));
			ans++;
		}		
	}
	if (p.at(N - 1) == N) {
		swap(p.at(N - 2), p.at(N - 1));
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
#include<stdio.h>

int main(void) {
	short pasta[100];
	unsigned long long int dp[100][3][2];
	unsigned long long int sum = 0;
	const int mods = 10000;
	int i, j, n, k, in1, in2;

	scanf("%d %d", &n, &k);
	for(i = 0; i < 100; i++) pasta[i] = 0;
	while(k--) {
		scanf("%d %d", &in1, &in2);
		pasta[in1 - 1] = in2;
	}

	/*set initial value*/
	if(pasta[0] == 0) {
		for(i = 0; i < 3; i++) dp[0][i][0] = 1;
		for(i = 0; i < 3; i++) dp[0][i][1] = 0;
	} else {
		for(i = 0; i < 3; i++) dp[0][i][0] = 0;
		for(i = 0; i < 3; i++) dp[0][i][1] = 0;
		dp[0][pasta[0] - 1][0] = 1;
	}

	/* Calculation*/
	for(i = 1; i < n; i++) {
		if(pasta[i] == 0) {
			dp[i][0][0] = (dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][2][0] + dp[i - 1][2][1]) % mods;
			dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][2][0] + dp[i - 1][2][1]) % mods;
			dp[i][2][0] = (dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][0][0] + dp[i - 1][0][1]) % mods;
			dp[i][0][1] = dp[i - 1][0][0] % mods;
			dp[i][1][1] = dp[i - 1][1][0] % mods;
			dp[i][2][1] = dp[i - 1][2][0] % mods;
		} else {
			for(j = 0; j < 3; j++) {
				if(j == pasta[i] - 1) {
					dp[i][j][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][2][0] + dp[i - 1][2][1] - dp[i - 1][j][0] - dp[i - 1][j][1]) % mods;
					dp[i][j][1] = dp[i - 1][j][0];
				} else {
					dp[i][j][0] = dp[i][j][1] = 0;
				}
			}
		}
	}

	sum = 0;
	for(i = 0; i < 6; i++) sum += dp[n - 1][i % 3][i % 2];
	sum %= mods;
	printf("%llu\n", sum);

	return 0;
}

Measured memory_bytes: 604
from fractions import gcd

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

def lcm(x, y):
    return (x * y) // gcd(x, y)

mod = 1
for i in range(len(A)):
    mod = lcm(mod, A[i])
mod -= 1
# print(mod)
ans = 0
for i in range(len(A)):
    ans += mod % A[i]
print(ans)

Measured memory_bytes: 5344
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main(void) {
	int N,M,K,temp;
	cin >> N >> M;
	vector< vector<int> > ps(N);
	vector< vector<int> > ls(M);
	for (int i = 0; i < N; ++i) {
		cin >> K;
		for (int j = 0; j < K; ++j) {
			cin >> temp;
			ps[i].push_back(temp-1);
			ls[temp-1].push_back(i);
		}
	}

	vector<bool> spkp(N,false);
	vector<bool> spkl(M,false);
	bool nf = true;
	bool mode = true;
	int pn,ln;
	queue<int> pars,lang;
	pars.push(0);
	while (nf) {
		nf = false;
		if (mode) {
			while (!pars.empty()) {
				pn = pars.front();
				pars.pop();
				for (size_t i = 0; i < ps[pn].size(); ++i) {
					if (!spkl[ps[pn][i]]) {
						nf = true;
						lang.push(ps[pn][i]);
						spkl[ps[pn][i]] = true;
					}
				}
			}
		}
		else {
			while (!lang.empty()) {
				ln = lang.front();
				lang.pop();
				for (size_t i = 0; i < ls[ln].size(); ++i) {
					if (!spkp[ls[ln][i]]) {
						nf = true;
						pars.push(ls[ln][i]);
						spkp[ls[ln][i]] = true;
					}
				}
			}
		}
		mode = !mode;
	}

	bool find = false;
	for (int i = 0; !find && i < N; ++i) {
		if (!spkp[i]) {
			find = true;
		}
	}

	if (find) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}

	return 0;
}


Measured memory_bytes: 8952
/*****/

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <iomanip>	//cout << fixed << setprecision(桁数);
#include <stdexcept>

using namespace std;
using ll = long long;

#define nextline() (std::cerr << "\n")
#define debug(x) (#x " : " + (x))
#define debug_cout(x) (std::cerr << #x << " : " <<  (x) << "\n")
#define debug_tabCout(n, x) (std::cerr << strMulti("\t",n) << #x << " : " <<  (x) << "\n")
#define debug_headCout(h, x) (std::cerr << h << " : " <<  (x) << "\n")
#define debug_tabHeadCout(n, h, x) (std::cerr << strMulti("\t",n) << h << " : " <<  (x) << "\n")

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; i++)
#define rep1(i, n) for(int i=1, i##_len=(n); i<=i##_len; i++)
#define rrep(i, n) for(int i=(n)-1; i >= 0; i--)
#define rrep1(i, n) for(int i=(n); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define pair(a, b) make_pair(a, b);
//#define int long long
constexpr int INF = 2000000100;
constexpr ll DIV = 1000000007;	// 10e9+7
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> T divUp(T a, T b) { if (a % b == 0) { return a / b; } return a / b + 1; }
std::string strMulti(std::string t, int n) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; }
template<class T> T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; }
template<class T> T math_C(T m, T n) { T ret = mathP(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; }
template<class T> bool compare_by_b(pair<T, T> a, pair<T, T> b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; }
template<class T> T math_gcd(T a, T b) { a = abs(a); b = abs(b); if (a < b) { std::swap(a, b); } T tmp; while (b != 0) { tmp = b; b = a % b; a = tmp; } return a; }
template<class T> T math_lcm(T a, T b) { a = abs(a); b = abs(b); if (a > b) { std::swap(a, b); } if (a == 1) { return b; } T i = a; while (i % b != 0) { i += a; } return i; }

/*****/

void Main()
{
	ll N, M;
	cin >> N >> M;
	vector<bool> w(N + 10, true);
	rep(i, M)
	{
		int x;
		cin >> x;
		w[x] = false;
	}

	vector<ll> dp(N + 10);
	dp[0] = 1;

	for (int i = 0; i < N; i++)
	{
		if (dp[i] >= DIV)
			dp[i] %= DIV;

		if (w[i + 1])
			dp[i + 1] += dp[i];
		if (w[i + 2])
			dp[i + 2] += dp[i];
	}

	dp[N] %= DIV;

	cout << dp[N];
}

/*****/

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

	//std::cout << std::fixed << std::setprecision(10);

	Main();

	return 0;
}


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

int main (){
	int x,y,s;
	while(cin>>x>>y>>s && x){
		int ans=0;
		for(int i=1;i<s;i++){
			for(int j=1;j<s;j++){
				if(i*(100+x)/100+j*(100+x)/100==s){ //xの税率でs円になれば
					ans=max(ans,i*(100+y)/100+j*(100+y)/100); //税率をyに変えてansを更新
				}
			}
		}
		cout<<ans<<endl;
	}
}

/*
5 8 105
8 5 105
1 2 24
99 98 24
12 13 26
1 22 23
1 13 201
13 16 112
2 24 50
1 82 61
1 84 125
1 99 999
99 1 999
98 99 999
1 99 11
99 1 12
0 0 0
*/


Measured memory_bytes: 3012
#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define int long long int
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};
 
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int n;
int a[100];
int dp[100001];

int play(int k) {
	if (k < 0)
		return 1;
	if (k == 0)
		return 0;
	if (dp[k] != -1)
		return dp[k];
	dp[k] = 0;
	for (int i = 0; i < n; i++) {
		int win = play(k-a[i]);
		if (win == 0) {
			dp[k] = 1;
			break;
		}
	}
	return dp[k];
}

void solve() {
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i <= k; i++) {
		dp[i] = -1;
	}
	if (play(k))
		cout << "First";
	else
		cout << "Second";
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
  
	return 0;
}

Measured memory_bytes: 9092
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MS2020C
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] NK = Console.ReadLine().Split(' ');
            int N = int.Parse(NK[0]);
            int K = int.Parse(NK[1]);
            string[] input = Console.ReadLine().Split(' ');
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(input[i]);
            }
            for(int i = 0; i < N - K; i++)
            {
                if (A[i] < A[i + K])
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
        }
    }
}


Measured memory_bytes: 45644
#include<iostream>
using namespace std;
int main()
{
    int N;
    scanf("%d", &N);

    int i;
    for (i = 0; i <= N/7; i++) {
        if ((N - 7*i) % 4 == 0) {
            printf("Yes");
            return 0;
        }
    }
    printf("No");
    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++)

int main(){

    int n;
    cin >> n;
    vector<int> t(n, 0);
    int a;

    rep(i, n-1) {
        cin >> a;
        a--;
        t[a]++;
    }
    
    rep(i, n) {
        cout << t[i] << endl;
    }

    return 0;
} 


Measured memory_bytes: 4032
// 0bd35dc5e428754fa574049b6be8efe0

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef pair<int, int> pii;

const int MAXN = (int) 1e5;

int n;

int A[MAXN + 5];
char type[MAXN + 5];

inline char safe_getchar()
{
	register char ch(getchar());
	while(!isgraph(ch)) ch = getchar();
	return ch;
}

inline void input()
{
	n = read<int>();
	type[1] = '+';
	for(int i = 1; i <= n; ++i)
	{
		if(i > 1) type[i] = safe_getchar();
		A[i] = read<int>();
	}
}

inline void solve()
{
	LL suf = 0;
	for(int i = 1; i <= n; ++i) suf += A[i];

	LL ans = LLONG_MIN, pre = 0;
	for(int i = 1, j; i <= n; i = j)
	{
		LL res = A[i];
		suf -= A[i];
		for(j = i + 1; type[j] == '+'; ++j) res += A[j], suf -= A[j];

		if(i > 1)
		{
			chkmax(ans, pre - res + suf);
			pre += res - A[i] - A[i];
		}
		else pre += res;
	}
	chkmax(ans, pre);

	printf("%lld\n", ans);
}

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("E.in", "r", stdin);
//	freopen("E.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}



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

using namespace std;

const int MOD = 1e9 + 7;

int main() {
  	int n;
  	cin >> n;
  	int a[n];
  	for (int& x : a)
      	cin >> x;
  	sort(a, a + n);
  	vector<int> ch;
  	if (n & 1)
      	ch.push_back(0);
  	for (int i = (n & 1 ? 2 : 1); i < n; i += 2)
    	ch.push_back(i), ch.push_back(i);
  	for (int i = 0; i < n; i++)
      if (a[i] != ch[i])
        	cout << 0, exit(0);
 	long long ans = 1;
  	n /= 2;
  	while (n--)
      ans = (ans * 2) % MOD;
  	cout << ans;
}

Measured memory_bytes: 1276