akhauriyash/Code-Regression huggingface dataset:
n,a,b=map(int,input().split())
mod = 10**9+7 #998244353 # 変える
MOD = 10**9+7 #素数 変える場所 
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
ans=power_func(2,n,mod)
c1=ModInt(1)
for i in range(n,n-a,-1):
    c1*=ModInt(i)
for i in range(1,a+1):
    c1/=ModInt(i)
c2=ModInt(1)
for i in range(n,n-b,-1):
    c2*=ModInt(i)
for i in range(1,b+1):
    c2/=ModInt(i)
print(ModInt(ans)-c1-c2-1)

Measured memory_bytes: 44380
from math import factorial
N, M = map(int, input().split())
diff = abs(N-M)
ans = -1
mod = 10**9+7
if diff >= 2:
  ans = 0
elif diff == 1: # oxoxo
  ans = factorial(N) * factorial(M)
elif diff == 0: # oxox / xoxo
  ans = 2 * factorial(N) * factorial(M)
print(ans%mod)

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

int main(){
  string str;
  cin >> str;
  vector<int> c(str.size());
  for(int i=0;i<str.size();i++){
    c.at(i)=(int)str.at(i);
  }
  sort(c.begin(),c.end());
  bool A=1;
  for(int i=0;i<str.size()-1;i++){
    if (c.at(i)==c.at(i+1)){
      cout << "no" << endl;
      A=0;
      break;
    }
  }
  if(A){
    cout << "yes" << endl;
  }
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline


def main():
    n = int(input())

    l = [str(i) for i in range(1, n + 1)]
    count = 0
    for i in l:
        if len(i) % 2 == 1:
            count += 1

    print(count)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9368
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn f(n: usize) -> usize {
    if n == 0 {
        return 0;
    }
    let res = n % pop_count(n);
    f(res) + 1
}

fn pop_count(n: usize) -> usize {
    let mut res = 0;
    let mut n = n;
    while n > 0 {
        res += n % 2;
        n /= 2;
    }
    res
}

fn solve() {
    input! {
        n: usize,
        x: Chars
    };

    let x = x
        .into_iter()
        .map(|ch| ch.to_digit(10).unwrap() as usize)
        .collect::<Vec<_>>();
    let mut pc = 0;
    for n in 0..n {
        if x[n] == 1 {
            pc += 1;
        }
    }
    let sum_mod_plus = x.iter().copied().fold(0, |acc, x| (acc * 2 + x) % (pc + 1));
    let sum_mod_minus = x.iter().copied().fold(0, |acc, x| {
        if pc <= 1 {
            return 0;
        }
        (acc * 2 + x) % (pc - 1)
    });
    let digits_val_mod_plus = (0..n)
        .into_iter()
        .scan(1, |acc, _| {
            let res = *acc;
            *acc = (*acc * 2) % (pc + 1);
            Some(res)
        })
        .collect::<Vec<_>>();
    let digits_val_mod_minus = (0..n)
        .into_iter()
        .scan(1, |acc, _| {
            if pc <= 1 {
                return Some(0);
            }
            let res = *acc;
            *acc = (*acc * 2) % (pc - 1);
            Some(res)
        })
        .collect::<Vec<_>>();
    for i in 0..n {
        if x[i] == 0 {
            let res = (sum_mod_plus + digits_val_mod_plus[n - i - 1]) % (pc + 1);
            let res = 1 + f(res);
            println!("{}", res);
        } else {
            let res = if pc == 1 {
                0
            } else {
                let res = ((pc - 1) + sum_mod_minus - digits_val_mod_minus[n - i - 1]) % (pc - 1);
                1 + f(res)
            };
            println!("{}", res);
        };
    }
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 6492
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kamol Paul
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define long long long
typedef pair < long , long > pii;

class AServalVsMonster {
public:
	void solve(std::istream& in, std::ostream& out) {
	    long x,y;
	    in>>x>>y;
	    out<<(x+y-1)/y<<endl;

	}
};


int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	AServalVsMonster solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#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 repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

bool is_prime(int n)
{
    if (n <= 1) return false;
    for (int i=2; i*i<=n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main(){
    int x;
    cin >> x;
    while (!is_prime(x)) x++;
    cout << x << endl;
    return 0;
}



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

int main(void){
    ll n,m; cin >> n >> m;
    ll max_z = m/1000;
    for(ll x=0;x<=n;x++){
        for(ll y=0;y<=n;y++){
            ll z = max_z-(5*y)-(10*x);
            if(x+y+z==n && 0 <= min(x,min(y,z))){
                cout << x << ' ' << y << ' ' << z << endl;
                return 0;
            }
        }
    }

    cout << -1 <<' ' <<  -1 << ' ' << -1 << endl;
    return 0;
}

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

#define VER 1
#define HOL 2

using namespace std;

typedef long long ll;

int main(void) {
    
    int n;
    vector<int> v;
    string s1, s2;
    
    cin >> n >> s1 >> s2;
    
    for (int i = 0; i < n; ++i) {
        
        if (i + 1 == n || s1[i] != s1[i + 1]) {
            
            v.push_back(VER);
            
        } else {
            
            v.push_back(HOL);
            
            ++i;
            
        }
        
    }
    
    ll ans;
    int pre;
    
    if (v[0] == VER) {
        
        ans = 3;
        
        pre = VER;
        
    } else {
        
        ans = 6;
        
        pre = HOL;
        
    }
    
    for (int i = 1; i < v.size(); ++i) {
        
        if (pre == VER) {
            
            ans *= 2;
            
            if (v[i] == HOL) {
                
                pre = HOL;
                
            }
            
        } else {
            
            if (v[i] == VER) {
                
                pre = VER;
                
            } else {
                
                ans *= 3;
                
            }
            
        }
        
        ans %= 1000000007;
        
    }
    
    cout << ans << endl;
    
    
    return 0;
    
}



























Measured memory_bytes: 256
s = input()
start = 0
end = 0
for i in range(len(s)):
    if s[i] == 'A':
        start = i
        break
for i in range(len(s)-1, 0, -1):
    if s[i] == 'Z':
        end = i + 1
        break
print(end - start)

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

class Fruit {
  public:
    string name;
    double efficiency;
    Fruit(string _name, double _efficiency):
      name(_name),
      efficiency(_efficiency) {
    }
};

int main() {
  int N;
  while(cin >> N, N) {
    vector<Fruit> fruits;
    for(int n = 0; n < N; ++n) {
      string name;
      cin >> name;
      int seedCost;
      cin >> seedCost;
      int aTime = 0;
      int aFromLeafTime = 0;
      for(int i = 0; i < 5; ++i) {
        int t;
        cin >> t;
        aTime += t;
        if(i > 2) aFromLeafTime += t;
      }
      int nfruit;
      cin >> nfruit;
      int aFruitPrice;
      cin >> aFruitPrice;
      int ngrow;
      cin >> ngrow;
      int tTime;
      tTime = aTime + aFromLeafTime * (ngrow - 1);
      int price;
      price = aFruitPrice * nfruit * ngrow;
      int income;
      income = price - seedCost;
      double efficiency;
      efficiency = (double)income / (double)tTime;
      Fruit fruit(name, efficiency);
      fruits.push_back(fruit);
    }
    sort(fruits.begin(), fruits.end(), [](Fruit left, Fruit right) {
      if(left.efficiency == right.efficiency) return left.name < right.name;
      return left.efficiency > right.efficiency;
    });
    for(int i = 0; i < N; ++i) cout << fruits[i].name << endl; //cout << fruits[i].name << " " << fruits[i].efficiency << endl;
    cout << '#' << endl;
  }
  return 0;
}

Measured memory_bytes: 1220
/**
 * @Author:      G_bg
 * @DateTime:    2019-08-10 19:59:57
 * @Description: 
 */
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI = 3.1415926535898;
const double E = 2.718281828459;
const int INF = 0x7fffffff;
const int mod = 1e9+7;
const int maxn = 1e5+10;
int main(int argc, const char *argv[]) {
    ios::sync_with_stdio(0);cin.tie(0);
    int a,b;cin >> a >> b;
    int ma = max(a+b,max(a-b,a*b));
    cout << ma << endl;
    // system("pause");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int c=0;
  int64_t a=0;
  int64_t m=0;
  for(int t=3;a<=n;t++){
    a=0;
    int x=t;
    vector<int> d;
    set<int> p;
    while(x>2){
      d.push_back(x%3*2+3);
      p.insert(x%3);
      x/=3;
    }
    for(int i=d.size()-1;i>=0;i--)
      a=a*10+d.at(i);
    if(p.size()==3&&a<=n&&a>m)
      c++;
    m=max(m,a);
  }
  cout<<c<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int Points(int n,int abc[][3]){
    int dp[n+1][3];
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;
    dp[1][0]=abc[0][0];
    dp[1][1]=abc[0][1];
    dp[1][2]=abc[0][2];
    for(int i=2;i<=n;i++){
            dp[i][0]=max(dp[i-1][1],dp[i-1][2])+abc[i-1][0];
            dp[i][1]=max(dp[i-1][0],dp[i-1][2])+abc[i-1][1];
            dp[i][2]=max(dp[i-1][0],dp[i-1][1])+abc[i-1][2];          
    }

    int ans=max(dp[n][1],max(dp[n][0],dp[n][2]));
    
    return ans;

}
int main() {
     int n;
     cin>>n;
     int abc[n][3];
     for(int i=0;i<n;i++){
         for(int j=0;j<3;j++){
             cin>>abc[i][j];
         }
     }
     cout<<Points(n,abc);

}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define P pair<int,int>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define re(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007;
int n;
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    cin>>n;
    int b,c;
    cin>>b>>c;
    int k=n-b;
    if(k>c){
        cout<<0<<endl;
    }
    else{
        cout<<c-k<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    string S, T;
    cin >> S >> T;
    int mi = INF;
    int slen = S.size();
    int tlen = T.size();
    for (int i = 0; i <= slen - tlen; i++) {
        int cnt = 0;
        for (int j = 0; j < tlen; j++) {
            if (S[i + j] == T[j]) cnt++;
        }
        mi = min(mi, tlen - cnt);
    }
    cout << mi << '\n';
}


Measured memory_bytes: 3628
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n;
    
    cin >> n;
    
    int houses[n];
    
    for(int i = 0; i < n; i++){
        cin>>houses[i];
    }
    
    sort(houses, houses+n);
    
    cout << (houses[n-1]-houses[0]);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
const int INF = 1e15;
using Graph = vector<vector<int>>;

signed main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for( int i = 0; i < N; i++ ) cin >> A.at(i);

  int ans = 0;
  int now = 1;
  for( int j = 0; j <= 60; j++ ){
    int k = 1LL << j;
    int one = 0;
    for( int i = 0; i < N; i++ ){
      if( A[i] & k ) one++;
    }

    ans += (one*(N-one))%MOD * now % MOD;
    ans %= MOD;
    now *= 2;
    now %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
//const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

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

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

mint f(int n) {
  if (n == 0) return 1;
  mint x = f(n/2);
  x *= x;
  if (n%2 == 1) x *= 2;
  return x;
}

mint choose(int n, int a) {
  mint x = 1, y = 1;
  rep(i,a) {
    x *= n-i;
    y *= i+1;
  }
  return x / y;
}


int main() {
    int n; cin >> n;
    int ans = 0;
    repp(i,n+1,1){
        if (1 <= i && i <= 9) ans++;
        else if (100 <= i && i <= 999) ans++;
        else if (10000 <= i && i <= 99999) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

 using namespace std;

 int main()
{
   int i, h, m, s;
   cin >> i;
   h = i / 3600;
   m = i % 3600 / 60;
   s = i % 3600 % 60;
   cout << h << ":" << m << ":" << s << endl; 
   
   return 0;
}


Measured memory_bytes: 3084
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    // make io faster https://gist.github.com/rigibun/7905920
	cin.tie(0);
   	ios::sync_with_stdio(false);
    const auto endl = "\n";

    ll n;
    cin >> n;
    vector<ll> a1(n);
    vector<ll> a2(n);
    for (ll i = 0; i < n; ++i) cin >> a1[i];
    for (ll i = 0; i < n; ++i) cin >> a2[i];
    for (ll i = 1; i < n; ++i) {
        a1[i] += a1[i-1];
        a2[n-i-1] += a2[n-i];
    }
    for (ll i = 0; i < n; ++i) {
        a1[i] += a2[i];
    }
    sort(a1.begin(), a1.end());
    cout << a1[n-1] << endl;
}


Measured memory_bytes: 256
N = int(input())
L1 = [0] + list(map(int, input().split()))
L2 = [0] + list(map(int, input().split()))
s = sum(L2)
a = 0
for i in range(1, N + 1):
    s += L1[i] - L2[i - 1]
    a = max(a, s)
print(a)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=998244353;
const int maxn = 1e5+7;

int n,m,a[maxn];

int main(){
    read(n);read(m);
    fo(i,1,n) read(a[i]);
    sort(a+1,a+1+n);
    LL ans=0;
    fo(i,1,m) ans+=a[i];
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>

void rotate(int* x0, int* y0, int* x1, int* y1, int* x, int* y){
    *x = (*y1 - *y0) + *x0;
    *y = -1 * (*x1 - *x0) + *y0;
}

int main(void){
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    int x3, x4, y3, y4;
    rotate(&x2, &y2, &x1, &y1, &x3, &y3);
    rotate(&x3, &y3, &x2, &y2, &x4, &y4);
    printf("%d %d %d %d\n", x3, y3, x4, y4);
    return 0; 
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef pair<ll,P>  PP;
typedef vector<ll> Vector;
typedef vector<Vector> DVector;
typedef priority_queue<PP, vector<PP>, greater<PP>> PPQueue;

#define fi          first
#define se          second
#define sfi         se.fi
#define sse         se.se
#define pb          push_back
#define INF         INT_MAX
#define bcnt        __builtin_popcount
#define all(x)      (x).begin(),(x).end()
#define uni(x)      x.erase(unique(all(x)),x.end())
#define ub(x,y)     (upper_bound(all(x),y)-x.begin())
#define lb(x,y)     (lower_bound(all(x),y)-x.begin())
#define rep(i,n)    repl(i,0,n-1)
#define usort(x)    sort(all(x))
#define dsort(x)    sort(all(x),greater<ll>())
#define mkp(x,y)    make_pair(x,y)
#define mmax(x,y)   (x>y?x:y)
#define mmin(x,y)   (x<y?x:y)
#define maxch(x,y)  x=mmax(x,y)
#define minch(x,y)  x=mmin(x,y)
#define exist(x,y)  (find(all(x),y)!=x.end())
#define each(itr,v) for(auto itr:v)
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
ll N, W;
vector<P> mp;
set<P> st;
map<P,ll> memo;
ll dfs(ll n, ll weight){
  P idx = mkp(n,weight);
  if(st.count(idx))return memo[mkp(n,weight)];
  if(n == N)return 0;
  ll res = dfs(n+1,weight);
  if(weight - mp[n].fi >= 0)maxch(res,mp[n].se+dfs(n+1,weight-mp[n].fi));
  st.insert(idx);
  return memo[idx] = res;
}

int main(){
  cin.sync_with_stdio(false);
  cin >> N >> W;
  rep(i,N){
    ll w,v;
    cin >> w >> v;
    mp.pb(mkp(w,v));
  }
  cout << dfs(0,W) << endl;
}


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

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

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

struct combination {
    vector<mint> fact, ifact;
    // init struct with "n" of "nCk" (maximum number in other words)
    combination(int n) : fact(n + 1), ifact(n + 1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    // c(n,k) returns mint that contains nCk (mod p (= 1e9+7)) in x
    // i.e.) mint num = c(n,k), then num.x == nCk (mod p (= 1e9+7))
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }

    // nPk - permutation
    mint p(int n, int k) {
        return fact[n] * ifact[n - k];
    }
};

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    combination nck(b);
    mint ans = mint(2).pow(n) - mint(1);

    mint apat = 1, bpat = 1;
    rep(i, a) apat *= n - i;
    rep(i, b) bpat *= n - i;
    apat *= nck.ifact[a];
    bpat *= nck.ifact[b];
    ans -= apat;
    ans -= bpat;
    cout << ans.x << endl;
}

Measured memory_bytes: 6292
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n,k = LI()
ans = 0
while n:
    n//=k
    ans+=1
print(ans)

Measured memory_bytes: 5328
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>

#define MOD 1000000007
#define REP(i,n) for ((i)=0;i<(n);i++)
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define LL long long
#define ULL unsigned long long



int main(void) {
	LL a,b,temp;
	scanf("%lld %lld", &a, &b);

	if((a<0&&b>0)||a==0||b==0){
		printf("Zero\n");
	}else if(a<0&&b<0){
		if((b-a)%2==0){
			printf("Negative\n");
		}else{
			printf("Positive\n");
		}
	}else{
		printf("Positive\n");
	}
	return 0;
}

/* 最後の改行忘れるな！！ */


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <math.h>

#define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
#define FORC(cont, it) for(decltype((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

int main(){

	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int h[n];

    FOR(i,0,n){
        cin >> h[i];
    }

    int dp[n+5];

    dp[0] = 0;
    dp[1] = abs(h[0]-h[1]);

    FOR(i,2,n){
        dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
    }

    cout << dp[n-1] << endl;

	return 0;
}


Measured memory_bytes: 1024
open Batteries
let explode s = List.init (String.length s) (String.get s)
let _ = 
  let s = read_line () 
  in let rec r lst =
    match lst with
    | [] -> 0
    | first :: rest -> if first = '-' then -1 + r rest else 1 + r rest
  in Printf.printf "%d\n" (r @@ explode s)


Measured memory_bytes: 1024
import java.util.*;

class Main {
  public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();//next(文字列), nextDouble, nextLine(1行)とか
    int X = sc.nextInt();
    int Y = sc.nextInt();
    
    int[] ans = new int[N-1];
    int min = 10000;
    for(int i =1;i<N;i++){
      for (int j = i+1;j<N+1;j++){
        min = Math.min((Math.abs(j-i)),(Math.abs(X-i)+1+Math.abs(Y-j)));
        min = Math.min(min,Math.abs(Y-i)+1+Math.abs(X-j));
        ans[min-1]++;
      }
    }
    for(int k:ans){
      System.out.println(k);
    }
    
    
  }    
}



Measured memory_bytes: 22996
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using ll = long long;
using namespace std;
#define rep(i,n) for(int (i)=0;i<(n);i++)

int main() {
	int k;
	string s;
	cin >> k>>s;
	if (s.size() <= k)cout << s << endl;
	else {
		rep(i, k) {
			cout << s.at(i);
		}
		cout <<"..." <<endl;
	}
		
	return 0;
}

Measured memory_bytes: 3624
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
#define dis(p,q) ((p)*(p)+(q)*(q))
int main(){
  int i,j,k;
  int n;
  while(cin>>n,n){
    double x[300],y[300];
    for(i=0;i<n;++i)
      cin>>x[i]>>y[i];    
    int mx=1;
    for(i=0;i<n-1;++i){
      for(j=i+1;j<n;++j){
	double d=dis(x[i]-x[j],y[i]-y[j]);
	if(d<=4){
	  double cx,cy,a=atan2(y[i]-y[j],x[i]-x[j]);
	  int sm;
	  cx=(x[i]+x[j])/2+cos(a+M_PI/2)*sqrt(1-d/4);
	  cy=(y[i]+y[j])/2+sin(a+M_PI/2)*sqrt(1-d/4);
	  sm=2;
	  for(k=0;k<n;++k){
	    if(k!=i&&k!=j&&dis(x[k]-cx,y[k]-cy)<=1)
	      ++sm;
	  }
	  mx=max(mx,sm);
	  cx=(x[i]+x[j])/2+cos(a-M_PI/2)*sqrt(1-d/4);
	  cy=(y[i]+y[j])/2+sin(a-M_PI/2)*sqrt(1-d/4);
	  sm=2;
	  for(k=0;k<n;++k){
	    if(k!=i&&k!=j&&dis(x[k]-cx,y[k]-cy)<=1)
	      ++sm;
	  }
	  mx=max(mx,sm);
	}
      }
    }
    cout<<mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 976
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};

bool isprime(int N) {
	if(N == 1) return false;
	if(N == 2) return true;
	for(int i=2; i*i<=N; i++) {
		if(N % i == 0)
			return false;
	} return true;
}

int32_t main () {
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	vector<int> v;
	for(int i=1; i<=55555; i++)
		if(isprime(i) and i % 5 == 1)
			v.push_back(i);
	int n; cin>>n;
	for(int i=0; i<n; i++) {
		cout<<v[i]<<' ';
	} cout<<endl;
	return 0;
}

Measured memory_bytes: 256
import itertools
n,m = map(int,input().split())
mat = [[0]*n for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    mat[u-1][v-1] = 1
    mat[v-1][u-1] = 1

cnt = 0
arr = [i for i in range(1,n)]
for road in itertools.permutations(arr):
    start = 0
    for r in road:
        if mat[start][r] ==0:
            break
        else:
            start = r
    else:cnt+=1
print(cnt)


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

namespace AOJ1_8_A
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            string Answer = null;
            string s;
            for (int i = 0; i < str.Length; i++)
            {
                if (char.IsUpper(str, i))
                {
                    s = str.Substring(i,1).ToLower();
                }
                else if (char.IsLower(str, i))
                {
                    s = str.Substring(i,1).ToUpper();
                }
                else
                {
                    s = str.Substring(i, 1);
                }

                Answer = Answer + s;
            }

            Console.WriteLine(Answer);
        }
    }
}


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

int main() {
  int a, b;
  cin >> a >> b;
  if((a / 2) * 2 != a && (b / 2) * 2 != b){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n)for(int i=0;i<n;i++)



int main(void){

    int D,N;
    cin>>D>>N;
    int ans=1;
    int i;
    rep(i,D){
        ans*=100;
    }
    int temp = ans;
    if(N==100){
        N++;
    }
    ans = temp*N;

    cout << ans << endl;

    


    return 0;
}

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

using namespace std;

long long cost(vector<int> X, int p) {
    long long ans = 0;
    for (auto x : X) {
        ans += (x - p) * (x - p);
    }
    return ans;
}

int main() {
    int N;
    cin >> N;
    vector<int> X(N);
    for (auto &&x: X) cin >> x;
    auto tot = accumulate(X.begin(), X.end(), 0);

    cout << min({cost(X, tot / N), cost(X, tot / N + 1)}) << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int num=0;
	for(int i=1;i<=n;i++){
		int t;
		cin>>t;
		if(t%2!=0 && i%2!=0) num++;
	}
	cout<<num<<endl;
	return 0;
} 

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
#define Maxn 200007
int n,a[Maxn],b[Maxn];
priority_queue<pair<int,int> >pq;
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    while (!pq.empty()) pq.pop();
    for (int i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        if (b[i]!=a[i]) pq.push(make_pair(b[i],i));
    }
    long long ans=0LL;
    while (!pq.empty())
    {
        int i=pq.top().second;
        pq.pop();
        if (b[i]-b[(i+1)%n]-b[(i+n-1)%n]<a[i])
        {
            printf("%d\n",-1);
            return 0;
        }
        int tmp=b[(i+1)%n]+b[(i+n-1)%n],t;
        if (a[i]>=max(b[(i+1)%n],b[(i+n-1)%n]))
        {
            if (b[i]%tmp!=a[i]%tmp)
            {
                printf("%d\n",-1);
                return 0;
            }
            t=(b[i]-a[i])/tmp;
        } else t=(b[i]-max(b[(i+1)%n],b[(i+n-1)%n]))/tmp+1;
        b[i]-=t*tmp;
        if (b[i]<a[i])
        {
            printf("%d\n",-1);
            return 0;
        }
        if (b[i]!=a[i]) pq.push(make_pair(b[i],i));
        ans+=t;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 6704
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    double l;
    cin >> l;
    double ans = pow((l / 3), 3);
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int x,k,d,m,n,z;
	cin>>x>>k>>d;
	if(x<0)
	x=-x;
	m=x/d;
	n=x%d;
	if(m>=k)
	cout<<x-k*d;
	else
	{
		z=k-m;
		if(z%2==0)
		cout<<n;
		else
		cout<<d-n;
	}
}

Measured memory_bytes: 3592
/*
  author:@bhaskar_8998
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef vector<i64> vi;
typedef pair<int,int>ii;
typedef vector<ii> vii;
typedef map<int,int> mi;
#define all(A) (A).begin(),(A).end()
#define pb push_back
#define MOD 1000000007
#define ff first
#define ss second
#define deb(x) cerr<<#x<<" "<<x<<"\n";
#define fastio() {ios_base::sync_with_stdio(false);cin.tie(NULL);}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    fastio();
    clock_t beg=clock();
    int t=1;
    // cin>>t;
    while(t--){
      int n,k;
      cin>>k>>n;
      mi m;
      m.clear();
      for(int i=0,a;i<n;i++){
        cin>>a;
        m[a]+=1;
      }
      int xm=0;
      for(int i=0;;i++){
        int x=INT_MAX,y=INT_MAX;
        if(m[k-i]==0)x=k-i;
        if(m[k+i]==0)y=k+i;
        xm=min(x,y);
        if(xm>=0 && xm!=INT_MAX)break;
      }
      cout<<xm;

     
    }
    clock_t end=clock(); 
    fprintf(stderr, "\n%lf sec\n", (double)(end-beg)/(CLOCKS_PER_SEC));
    return 0;
}


  

Measured memory_bytes: 3828
#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)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep (i, h) cin >> s[i];
    vector<vector<int> > l(h, vector<int>(w)), r(h, vector<int>(w)), u(h, vector<int>(w)), d(h, vector<int>(w));
    rep (i, h) {
        int cnt = 0;
        rep (j, w) {
            if (s[i][j] == '#') cnt = 0;
            else cnt++;
            l[i][j] = cnt;
        }
    }
    rep (i, h) {
        int cnt = 0;
        for (int j = w - 1; j >= 0; --j) {
            if (s[i][j] == '#') cnt = 0;
            else cnt++;
            r[i][j] = cnt;
        }
    }
    rep (j, w) {
        int cnt = 0;
        rep (i, h) {
            if (s[i][j] == '#') cnt = 0;
            else cnt++;
            u[i][j] = cnt;
        }
    }
    rep (j, w) {
        int cnt = 0;
        for (int i = h - 1; i >= 0; --i) {
            if (s[i][j] == '#') cnt = 0;
            else cnt++;
            d[i][j] = cnt;
        }
    }
    int ans = 0;
    rep (i, h) {
        rep (j, w) {
            int tmp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3;
            ans = max(ans, tmp);
        }
    }
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 67328
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> A(N);
  priority_queue<ll> q;
  for (int i = 0; i < N; i++)
  {
    scanf("%lld", &A[i]);
    q.push(A[i]);
  }
  for (int i = 0; i < M; ++i)
  {
    ll t = q.top();
    q.pop();
    t /= 2;
    q.push(t);
  }
  ll ans = 0;
  while (!q.empty())
  {
    ans += q.top();
    q.pop();
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2296
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head
int q,m,n,k,res,tmp,tmp2;
int a[16][16] = {};
int b[200010] = {};
vector<pair<int,int>> v[305];
deque<PII> que;
int dp[305][305][305] = {};
string s;
int r[301][3];


signed main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
	std::cin >>n>>m;
	rep(i,0,m){
		cin>>r[i][0]>>r[i][1]>>r[i][2];
		v[r[i][1]].pb({r[i][0],r[i][2]});
	}
	dp[0][0][0] = 1;
	res = 0;
	rep(i,0,n+1){
		rep(j,0,n+1){
			rep(k,0,n+1){
				if (dp[i][j][k] == 0) continue;
				int x = max({i,j,k});
				for (auto l : v[x]){
					int right = x;
					int left = l.fi;
					int kazu = l.se;
					int count = 0;
					if (left <= i ) count += 1;
					if (left <= j ) count += 1;
					if (left <= k ) count += 1;
					if (kazu != count) dp[i][j][k] =0;
				}
				if (x == n){
					res += dp[i][j][k];
					res %= mod;
				}
				dp[x+1][j][k] += dp[i][j][k];
				dp[i][x+1][k] += dp[i][j][k];
				dp[i][j][x+1] += dp[i][j][k];
				dp[x+1][j][k] %= mod;
				dp[i][x+1][k] %= mod;
				dp[i][j][x+1] %= mod;
			}
		}
	}
	cout<<res<<endl;
}


Measured memory_bytes: 223488
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    static int[][] dp;
    static Scanner sc;

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        int n = sc.nextInt();
        int W = sc.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];

        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        dp = new int[n+1][W+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < W+1; j++) {
                int u = dp[i][j];
                if((j > w[i] && dp[i+1][j - w[i]] != 0) || j - w[i] == 0) {
                    dp[i+1][j] = Math.max(u, dp[i+1][j-w[i]] + v[i]);
                }
                else {
                    dp[i+1][j] = dp[i][j];
                }
            }
        }
        System.out.println(IntStream.of(dp[n]).max().getAsInt());
    }
}



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


int main()
{
    string s;
    cin>>s;
    string prev ,curr;
    prev.push_back(s[0]);
    int index =1;
    int ans =1;
    while( index < s.length() )
    {
        curr.push_back( s[index]);
        if( prev != curr )
        {
            ans++;
            prev = curr;
            curr.clear();
        }

        index++;
    }
    cout<<ans;
}

Measured memory_bytes: 3744
#include <iostream>
#include <cassert>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
 
using namespace std;
typedef long long ll;
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.1415926535897932384626;
long long int mod = 1000000007;
 
vector<ll> G[500005];
vector<P> tree[500010];
priority_queue <ll> pql;
priority_queue <P> pqp;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
//↓,→,↑,←
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<x;
#define re(i,a,b) for(i=a;i<=b;i++);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define deba(x) cout<< #x << " = " << x <<endl

ll rui(ll abc,ll bed){
	//abcのbed乗を計算する
	if(bed==0){return 1;}
	else{
		ll ced = rui(abc,bed/2);
		ced *= ced;
		ced %= mod;
		if(bed%2==1){ced*=abc; ced%=mod;}
		return ced;
	}
} 





ll i,j,k,ii,jj;
ll n,m,num,sumxor,sum,ans;
ll a,b,c,d,e,f,g,h,w,v;
ll x[800005],y[800005],z[900005];

int main(){	
	cin>>n;
	p(1110-n);


	return 0;
}

Measured memory_bytes: 24832
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	
	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
	
		int R = sc.nextInt(), C = sc.nextInt(), N = sc.nextInt();
		Point[] pts = new Point[N << 1];
		int sz = 0;
		for(int i = 0, j = 0; i < N; ++i)
		{
			Point p = new Point(sc.nextInt(), sc.nextInt()), q = new Point(sc.nextInt(), sc.nextInt());
			if(p.onBoundary(R, C) && q.onBoundary(R, C))
			{
				pts[sz << 1] = p;
				pts[sz << 1 | 1] = q;
				p.idx = q.idx = sz++;
			}
		}
		pts = Arrays.copyOf(pts, sz << 1);
		for(int i = 0; i < sz << 1; ++i)
			pts[i].setFrameIndex(R, C);
		Arrays.sort(pts);
		boolean possible = true, open[] = new boolean[sz];
		Stack<Integer> s = new Stack<>();
		for(Point p: pts)
			if(!open[p.idx])
			{
				open[p.idx] = true;
				s.push(p.idx);
			}
			else if(s.pop() != p.idx)
			{
				possible = false;
				break;
			}
		out.println(possible ? "YES" : "NO");
		out.close();
	}
	
	static class Point implements Comparable<Point>
	{
		int x, y, idx, frameIndex;
		
		Point(int a, int b) { x = a; y = b; }
		
		boolean onBoundary(int R, int C) { return x == 0 || x == R || y == 0 || y == C; }
		
		void setFrameIndex(int R, int C)
		{
			if(y == 0)
				frameIndex = x;
			else if(x == R)
				frameIndex = R + y;
			else if(y == C)
				frameIndex = R + C + R - x;
			else
				frameIndex = R + C + R + C - y;
		}
		
		public int compareTo(Point p) { return frameIndex - p.frameIndex; }
	}
		
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}

		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}

		public double nextDouble() throws IOException { return Double.parseDouble(next()); }

		public boolean ready() throws IOException {return br.ready();} 
	}
}

Measured memory_bytes: 49988
## C - Train Ticket
A,B,C,D = input()
for i in range(2):
    op1 = 1 if i == 0 else -1
    for j in range(2):
        op2 = 1 if j == 0 else -1
        for k in range(2):
            op3 = 1 if k == 0 else -1
            if(int(A) + int(B) * op1 + int(C) * op2 + int(D) * op3 == 7):
                op1t = '+' if op1 == 1 else '-'
                op2t = '+' if op2 == 1 else '-'
                op3t = '+' if op3 == 1 else '-'
                print(str(A) + op1t + str(B) + op2t + str(C) + op3t + str(D) + '=7')
                break
        else:
            continue
        break
    else:
        continue
    break

Measured memory_bytes: 3064
import sys
M = 10**9 + 7
x, y = map(int, input().split())

# (1, 2) * a + (2, 1) * b = (x, y)
#
# a + 2 * b = x
# 2 * a + b = y
# b = y - 2 * a
# a = x - 2 * b
# b = y - 2 * (x - 2 * b)
#   = y - 2 * x + 4 * b
# 3 * b = - y + 2 * x

b = (-y + 2*x)# / 3
if b % 3 != 0 or b < 0:
    print(0)
    sys.exit()
b //= 3
a = x - 2 * b
# (a + b)! / (a! * b!)
if a < 0:
    print(0)
    sys.exit()
if a == 0 or b == 0:
    print(1)
    sys.exit()

def fact(n):
    ans = n
    for i in range(1, n):
        ans *= i
        if ans >= M:
            ans %= M
    return ans

def pm(value, n):
    if n == 0:
        return 1
    if n % 2:
        return pm(value, n - 1) * value % M
    else:
        return pm(value, n // 2) ** 2 % M

# A * B ^ (M-2)
print(fact(a + b) * pm(fact(a) * fact(b) % M, M - 2) % M)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int N,M;
ll X[101010],K;
int A[62][101010], dy[101010];

int main(){
  cin>>N;
  rep(i,N) cin>>X[i];
  rep(i,N-1) A[0][i]=dy[i]=i;
  cin>>M>>K;
  rep(i,M){
    int x; cin>>x; x--;
    swap(A[0][x-1],A[0][x]);
  }
  rep(i,61){
    rep(j,N){
      A[i+1][j]=A[i][A[i][j]];
    }
  }
  
  rep(i,61){
    if(K&(1LL<<i)){
      rep(j,N) dy[j]=A[i][dy[j]];
    }
  }
  ll sum=X[0];
  rep(i,N){
    cout<<sum<<endl;
    sum+=X[dy[i]+1]-X[dy[i]];
  }
  return 0;
}


Measured memory_bytes: 26880
from collections import deque

if __name__ == "__main__":
    s = input()
    ans = deque()
    for ss in s:
        ans.append(ss)
    q = int(input())
    revflag = False

    for i in range(q):
        tmp = input().split()
        if tmp[0] == '1':
            if revflag:
                revflag = False
            else:
                revflag = True
        else:
            if tmp[1] == '1' and revflag:
                ans.append(tmp[2])
            elif tmp[1] == '1' and not revflag:
                ans.appendleft(tmp[2])
            elif tmp[1] == '2' and revflag:
                ans.appendleft(tmp[2])
            else:
                ans.append(tmp[2])

    if revflag:
        print(''.join(reversed(ans)))
    else:
        print(''.join(ans))


Measured memory_bytes: 8564
#include <iostream>
#include <map>
#include <string>
int main() {
	int n;
	std::cin >> n;
	std::map<std::string, int> map;
	for (auto i = 0; i < n; ++i) {
		int o, x;
		std::string str;
		std::cin >> o >> str;
		switch (o) {
		case 0: std::cin >> x; map[str] = x; break;
		case 1: std::cout << map[str] << std::endl; break;
		default: map.erase(str);
		}
	}
}


Measured memory_bytes: 27820