akhauriyash/Code-Regression huggingface dataset:
from itertools import product
from collections import deque

class ZeroOneBFS:
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        
    def add_edge(self, init, end, weight, undirected=False):
        assert weight in [0, 1]
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
        
    def distance(self, s):
        self.order = [-1] * self.N # a bfs ordering of each vertex
        self.dist = [-1] * self.N # the distance of each vertex from s
        dq = deque([(s, 0)]) # (vertex, dist)
        num = 0 # current ordering
        while dq:
            v, d = dq.popleft()
            if self.order[v] < 0: # visited v for the first time
                self.order[v] = num; self.dist[v] = d
                num += 1
                for u, w in self.E[v]:
                    if self.order[u] >= 0: continue
                    if w == 0: dq.appendleft((u, d))
                    else: dq.append((u, d+1))
        return self.order, self.dist

H, W = map(int, input().split())
zobfs = ZeroOneBFS(H * W)

def vtx(i, j): return i*W + j
def coord(n): return divmod(n, W)

grid = [input() for _ in range(H)] # |string| = W
E = [[] for _ in range(H * W)]
ans = 0 if grid[0][0] == '.' else 1
for i, j in product(range(H), range(W)):
    v = vtx(i, j)
    check = [vtx(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for u in check:
        x, y = coord(u)
        if grid[i][j] == '.' and grid[x][y] == '#':
            zobfs.add_edge(v, u, 1)
        else:
            zobfs.add_edge(v, u, 0)
_, dist = zobfs.distance(0)
ans += dist[vtx(H-1, W-1)]
print(ans)

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

int main() {
  vector<vector<int>> a(3, vector<int>(3));
  rep(i,3) {
    rep(j,3) {
      cin >> a[i][j];
    }
  }
  int n; cin >> n;
  vector<int> b(n);
  rep(i,n) cin >> b[i];
  rep(i,n) {
    rep(j,3) {
      rep(k,3) {
        if (b[i] == a[j][k]) a[j][k] = 0;
      }
    }
  }
  bool ans = false;
  rep(i,3) {
    if (a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0) ans = true;
  }
  rep(i,3) {
    if (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0) ans = true;
  }
  if (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0) ans = true;
  if (a[0][2] == 0 && a[1][1] == 0 && a[2][0] == 0) ans = true;
  if (ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
// AtCoder-Template.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second
#define FOR(i,N) for(auto i=0; i<N; ++i)
#define FORREV(i,N,_cnt) for(auto i=N-1,cnt=_cnt; cnt > 0; --i, --cnt)
#define ALL(x) x.begin(), x.end()

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T& a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T& a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
	ifstream ifs("in.txt");
	cin.rdbuf(ifs.rdbuf());
#endif
	ll N; cin >> N; vector<ll> A(N); FOR(i, N) cin >> A[i];
	sort(ALL(A), greater<ll>{});
	
	vector<ll> TwoPowers;	ll init = 2;	while (init < 3e9 + 10) {		TwoPowers.push_back(init);		init *= 2;	}
	set<ll> setTwoPowers(ALL(TwoPowers));
	map<ll, ll> cnt;	for (auto a : A) cnt[a] += 1;
	
	ll ans = 0;
	FOR(i, N) { 
		// ちいさいほうからとると 1 1 1 1 3 3 3 3 のときに、1,1 をくっつけてしまう

		auto a = A[i]; // 大きいAの値から。1023だった場合は、1を探したい。
		auto tit = upper_bound(ALL(TwoPowers), a);//一番近い2べきを探す	
		

		if (*tit == a * 2 and cnt[a] >= 2) {
			ans += 1; cnt[a] -= 2;
		}
		else if (*tit != a * 2 and cnt[*tit - a] >= 1 and cnt[a] >= 1) {
			ans += 1;
			cnt[*tit - a] -= 1;
			cnt[a] -= 1;
		}
	}
	cout << ans << endl;

	return 0;
}


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


Measured memory_bytes: 2104
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a) (a).begin(),(a).end()

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

  int h,w;
  cin >> h >> w;

  if(h%3==0||w%3==0)cout <<"0"<< endl;
  else if(h%2==0 && w%2==0) cout << min(h/2,w/2)<< endl;
  else if(h%2==0) cout << min(w,h/2) << endl;
  else if(w%2==0) cout << min(h,w/2) << endl;
  else {
      int b1=h/2,b2=w/2;
      int a1=h/3,a2=w/3;
      int x=max(2*a1+1,a1+b2+1);
      int y=max(2*a2+1,a2+b1+1);
      cout << min(min(h,w),min(x,y))<< endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

int main(){
    ll N,K;
    cin >> N >> K;

    ll kensa = 1;

    for(int i = 0;i < 20;i++)
        kensa *= 2;

    double goukei = 0.0;
    for(ll i = 1;i <= N;i++){
        int res = 0;
        ll hako = i;
        while(hako < K){
            hako *= 2;
            res++;
        }

        double keisan = 1;
        for(int j = 0;j < res;j++){
            keisan /= 2.0;
        }

        goukei += keisan / (double)N;

    }

    printf("%.12f\n",goukei);
}

Measured memory_bytes: 3732
//Name: One-Dimensional Cellular Automaton
//Level: 
//Category:
//Note:

/**
 */
#include <iostream>
#include <vector>
#include <string>
#include <array>

using namespace std;

typedef vector<int> MatRow;
typedef vector<vector<int>> Matrix;

void matmul(Matrix &a, const Matrix &b, int N, int M) {
    Matrix tmp(N, MatRow(N, 0));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            for(int k = 0; k < N; ++k) {
                tmp[i][j] += a[i][k] * b[k][j];
                tmp[i][j] %= M;
            }
        }
    }
    a = tmp;
}

bool solve() {
    int N, M, A, B, C, T;
    cin >> N >> M >> A >> B >> C >> T;
    if(!N && !M && !A && !B && !C && !T) return false;
    vector<int> init(N, 0);
    for(int i = 0; i < N; ++i) {
        cin >> init[i];
    }
    Matrix mat(N, MatRow(N, 0)), unit(N, MatRow(N, 0));
    for(int i = 0; i < N; ++i) {
        if(i > 0) mat[i][i-1] = A;
        mat[i][i] = B;
        if(i+1 < N) mat[i][i+1] = C;
    }
    for(int i = 0; i < N; ++i) {
        unit[i][i] = 1;
    }
    Matrix res(unit), ord(mat);
    while(T > 0) {
        if(T & 1) {
            matmul(res, ord, N, M);
        }
        matmul(ord, ord, N, M);
        T /= 2;
    }

    for(int i = 0; i < N; ++i) {
        int s = 0;
        for(int j = 0; j < N; ++j) {
            s += res[i][j] * init[j];
            s %= M;
        }
        if(i > 0) cout << " ";
        cout << s;
    }
    cout << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1304
#include <stdio.h>

int main(int argc, char const *argv[]) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    if(a < b && b < c) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 2056
# C

import math

N = int(input())

T = []
X = []
Y = []

for i in range(N):
    t, x, y = map(int, input().split())
    T.append(t)
    X.append(x)
    Y.append(y)


def l1_distance(p,q):
    return int(math.fabs(p[0] - q[0]) + math.fabs(p[1] - q[1]))


# first step
if l1_distance([0,0], [X[0],Y[0]]) <= T[0] and (T[0] - l1_distance([0,0], [X[0],Y[0]])) % 2 == 0:
    pass
else:
    print("No")
    quit()

for i in range(N-1):
    if l1_distance([X[i],Y[i]], [X[i+1],Y[i+1]]) <= T[i+1] - T[i] and (T[i+1] - T[i] - l1_distance([X[i],Y[i]], [X[i+1],Y[i+1]])) % 2 == 0:
        pass
    else:
        print("No")
        quit()

print("Yes")

Measured memory_bytes: 11792
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
 
typedef long long lli;

const int MAX = 59049; // 3 ^ 10
const lli MOD = 100000007;
 
int h,w,v[10][10];
int pow3[12];
 
int getbit(int bit, int pos){
  bit /= pow3[pos];
  return bit %= 3;
}
 
int setbit(int bit, int num, int pos){
  return bit - getbit(bit,pos) * pow3[pos] + num * pow3[pos];
}

int shiftleft(int bit){
  bit *= 3;
  return setbit(bit, 0, w);
}
 
void makepow(){
  pow3[0] = 1;
  for(int i=1;i<12;i++) pow3[i] = pow3[i-1] * 3;
}

void solve(){
  lli dp[2][3][MAX];

  fill(dp[0][0],dp[2][0],0);
  dp[0][0][0] = 1;
  
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      for(int k=0;k<3;k++){
        for(int l=0;l<pow3[w];l++){
          if(dp[0][k][l] == 0) continue;
          int up = getbit(l, w-1);
          int rem = v[i][j] - up - k;
          if(!v[i][j]) {
            if(k > 0 && up > 0) continue;
            rem = up + k;
          }
          for(int ri=0;ri<=min(2,rem);ri++){
            int bo = rem - ri;
            int next = setbit(shiftleft(l), bo, 0);
            if(bo > 2) continue;
            if(!v[i][j] && (up > 0 && ri > 0 || k > 0 && bo > 0)) continue;
            if(i < h - 1 && v[i+1][j] && bo > v[i+1][j] || i == h - 1 && bo > 0) continue;
            if(j < w - 1 && v[i][j+1] && ri > v[i][j+1] || j == w - 1 && ri > 0) continue;
            //cout << i << ' ' << j << ' ' << ri << ' ' << bo << endl;
            dp[1][ri][next] = (dp[1][ri][next] + dp[0][k][l]) % MOD;
          }
        }
      }
      for(int k=0;k<3;k++){
        for(int l=0;l<pow3[w];l++){
          dp[0][k][l] = dp[1][k][l];
          dp[1][k][l] = 0;
        }
      }
    }
  }

  int ans = 0;
  for(int i=0;i<3;i++)
    for(int j=0;j<pow3[w];j++)
      ans += dp[0][i][j];      
  cout << ans << endl;
}
 
int main(){
  makepow();

  while(cin >> h >> w){
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        char c;
        cin >> c;
        if(c == '.') v[i][j] = 0;
        else v[i][j] = c - '0';
      }
    }  
    solve();
  }
}

Measured memory_bytes: 3932
import java.util.Scanner;

/**
 * B - Comparing Strings
 * 1 桁の正整数 a ,b が与えられます。
 * 整数 a を b 回繰り返してできる文字列と 整数 b を a 回繰り返してできる文字列のうち、辞書順で小さい方を答えてください。
 */
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner( System.in );
        // 整数
        int a = sc.nextInt();
        int b = sc.nextInt();

        if( a <= b ) {
            String stringA = String.valueOf( a );
            for( int i = 1; i < b; i++ ) {
                stringA += a;
            }
            System.out.println( stringA );
        }
        else {
            String stringB = String.valueOf( b );
            for( int i = 1; i < a; i++ ) {
                stringB += b;
            }
            System.out.println( stringB );
        }

        sc.close();
    }
}

Measured memory_bytes: 21332
#![allow(non_snake_case, unused_macros, unused_imports)]

// Input
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

// Module
use std::cmp::{min,max};
use std::collections::{HashSet,BTreeMap,VecDeque};

// Main
fn main(){
    input!{
        N: usize,
        T: f64,
        A: f64,
        H: [f64; N],
    }
    let mut ans = 0;
    let mut d = 99999.0;
    let mut tmp;
    for i in 0..N{
        tmp = (A-(T - H[i]*0.006)).abs();
        if tmp < d{
            d = tmp;
            ans = i+1;
        }
    }
    println!("{}", ans);
}


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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

u64 lcm(u64 a, u64 b) { return (a / gcd(a, b)) * b; }

int main() {
  u32 N;
  cin >> N;
  string S;
  cin >> S;
  u32 res = 0;
  auto pos = S.find("ABC");
  while (pos != string::npos) {
    ++res;
    pos = S.find("ABC", pos + 3);
  }
  cout << res;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define ffrvs(ii,nn,mm) for(int ii=nn;ii>=mm;ii--)
#define srt(vvv) sort(vvv.begin(),vvv.end())
#define srtrvs(vvv) reverse(vvv.begin(),vvv.end())
#define Graph vector<vector<int>>
i64 inf = 1000000007;
i64 giant = 4000000000000000037;

using namespace std;

//メモリ置き場
int n, k;
string s;

//inputします
void input() {
	cin >> n >> k;
	cin >> s;
	k--;
}

//ライブラリ置き場



//main
int main() {
    input();
	int h = s[k] - 'A';
	char ne = 'a' + h;
	s[k] = ne;
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(int i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcount(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
ll gcd(ll a, ll b)
{
    return (b?gcd(b,a%b):a);
}
ll P(ll B, ll power, ll modulo)
{
    ll ans=1LL;
    while(power>0LL)
    {
        if(power%2LL==1LL)
        {
            ans=(ans*B)%modulo;
        }
        B=(B*B)%modulo;
        power/=2LL;
    }
    return ans;
}
bool isPrime(ll n)
{
    if(n<=1LL)
    {
        return false;
    }
    if(n<=3LL)
    {
        return true;
    }
    if(n%2==0LL || n%3==0LL)
    {
        return false;
    }
    for(ll i=5LL; (i*i)<=n; i+=6LL)
    {
        if(n%i==0LL || n%(i+2LL)==0LL)
        {
            return false;
        }
    }
    return true;
}
using namespace std;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
    return (a.second<b.second);
}
bool sortbysecll(const pll &a, const pll &b)
{
    return (a.second<b.second);
}
ll modinv(ll x, ll y, ll modulo)
{
    return ((x%modulo)*(P(y,modulo-2LL,modulo)%modulo))%modulo;
}
int main()
{
    FAST
    FO
    FI
    int n;
    IN n;
    vector<int> v(n);
    map<int,ll> m;
    loop(i,0,n)
    {
        IN v[i];
        m[v[i]]++;
    }
    ll ans=0;
    for(auto x:m)
    {
        if(x.second>1)
        {
            ans+=(((x.second)*(x.second-1))/2);
        }
    }
    loop(i,0,n)
    {
        ll temp=ans;
        if(m[v[i]]==1)
        {
            OUT ans<<endl
        }
        else
        {
            temp-=(((m[v[i]])*(m[v[i]]-1))/2);
            m[v[i]]--;
            temp+=(((m[v[i]])*(m[v[i]]-1))/2);
            m[v[i]]++;
            OUT temp<<endl
        }
    }
    return 0;
}


Measured memory_bytes: 11264
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const [L, R, d] = input[0].map(Number);

  let answer = 0;

  for (let i = L; i <= R; i++) {
    if (i % d === 0) {
      answer += 1;
    }
  }

  return answer;
};

console.log(main(read()));


Measured memory_bytes: 29680
"use strict"
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	//文字列から10進数に変換するときはparseIntを使います
  if(input[0]===input[1].slice(0,-1)){
console.log("Yes");
}else{
console.log("No");
}
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using vec_b = vector<bool>;
using vec_str = vector<string>;
using graph = mat;
using edge = pair<ll,ll>;
using wgraph = vector<vector<edge>>;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back


int main()
{
    ll N, K;
    cin >> N >> K;

    ll sum = 0;
    REP(i,K,N+2) sum = (sum + (i * (N - i + 1) + 1) % MOD) % MOD;
    _PR(sum);    



    return 0;
}

/*



*/

Measured memory_bytes: 3632
S = [int(s) if s != '?' else -1 for s in input().strip()]
mod = 10**9+7
dp = [0]*13
dp[0] = 1
cnt = 1
for i, s in enumerate(S[::-1]): 
    d = [0]*13
    if s == -1:
        for j in range(10):
            for k in range(13):
                d[(j*cnt+k)%13] = (d[(j*cnt+k)%13] + dp[k])%mod
    else:
        for k in range(13):
            d[(s*cnt+k)%13] = (d[(s*cnt+k)%13] + dp[k])%mod
    cnt = (cnt*10)%13
    dp = d[:]
print(dp[5])


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

using namespace std;

typedef long long ll;
typedef long double ld;
#define mems(p) memset(p,-1,sizeof(p))
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define nl "\n"

const int mxN = 1e6 + 1;
const ll MOD = 1e9 + 7;

void fast()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}

ll store[mxN][2][2];
int n;

ll dp(int idx, int get1, int get9) {
	if (idx >= n) {
		if (!get1 || !get9) return 0;
		return 1;
	}

	if (store[idx][get1][get9] != -1) return store[idx][get1][get9];
	ll res = 0;
	for (int i = 1; i < 9; ++i)
	{
		res += dp(idx+1, get1, get9);
		res %= MOD;
	}
	res += dp(idx+1, 1, get9);
	res %= MOD;
	res += dp(idx+1, get1, 1);
	res %= MOD;
	return store[idx][get1][get9] = res;
}

int main() {
	fast();
	cin >> n;
	mems(store);
	cout << dp(0, 0, 0) << nl;
}

Measured memory_bytes: 113000
#include <stdio.h>

int realgdcfunction(int a, int b) {
    // printf("now on gdc func\n");
    if (b==0) return a;
    else return realgdcfunction(b,a%b);
}


int givemegdc(int i, int j, int p) {
    // printf("now on giveme func\n");
    return realgdcfunction(p,realgdcfunction(i,j));
}

void ko(int k) {
    int ans=0;
    for(int i=1;i<=k;i++) {
        for(int j=1;j<=k;j++) {
            for(int p=1;p<=k;p++) {
                // printf("now on ko func\n");
                // printf("i%dj%dp%d\n",i,j,p);
                ans+=givemegdc(i,j,p);
            }
        }
    }
    printf("%d",ans);
    return 0;
}



int main () {
    int k;
    scanf("%d",&k);
    ko(k);
    return 0;
}

Measured memory_bytes: 1736
n,a,b=map(int,input().split())
s=input()
c=a+b
t=0
f=0
for i in range(n):
  if s[i]=='a':
    if t<c:
      print('Yes')
      t+=1
    else:
      print('No')
  elif s[i]=='b':
    if t<c and f<b:
      t+=1
      f+=1
      print('Yes')
    else:
      print('No')
  else:
    print('No')

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

typedef long long LL;

LL n,m;

int main()
{
	cin>>n>>m;
	if(n>m/2) cout<<m/2<<endl;
	else
	{
		m-=n*2;
		n+=m/4;
		cout<<n<<endl;
	}
}

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

#define rng(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define urng(i, a, b) for(int i = int(b) - 1; i >= int(a); i--)
#define urep(i, b) urng(i, 0, b)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed

int main() {
  int n, b;
  double ans = 0;
  //string s;
  cin >> n;
  vector<int> a(n);
  //if(1) {}
  rep(i, n) {
    cin >> a.at(i);
    ans += a.at(i);
  }
  ans /= n;
  ans = round(ans);
  b = ans;
  ans = 0;
  rep(i, n) ans += (b - a.at(i)) * (b - a.at(i));
  //for(int i = 0; i < n; i++){}
  cout << ans << endl;
}

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

using namespace std;

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

	long long x, y;

	cin >> x >> y;

	if(x % y) {
		cout << x << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f3f3f3f3fLL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
 
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
//ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int N;
string str;
ll dp[214514]={0};
int h[214514];
ll a[214514];
const int BT = 1 << 18 ;
struct segtree {//BT = size,2べき, 初期化忘れずに
	vector<ll> seg;
	
	void init() {
		seg.resize(BT * 2);
		rep(i, BT * 2 - 1) seg[i] = (ll)0;
	}
	
	void add(int pos, ll x) {//posにxを追加,0-index nodeも0-index
		pos += BT - 1;
		seg[pos] = x;
	
		while (pos > 0) {
			pos = (pos - 1) / 2;
			seg[pos] = max(seg[pos * 2 + 1], seg[pos * 2 + 2]);
		}
	}

	ll maxQ(int a, int b, int k = 0, int l = 0, int r = BT) {//[a,b)に対するクエリ
		if (b <= l || r <= a) return 0;//交差しない
		if (a <= l && r <= b) return seg[k];//被覆する
		return max(maxQ(a, b, k * 2 + 1, l, (l + r) / 2), maxQ(a, b, k * 2 + 2, (l + r) / 2, r));
	}

}segm; 
	
int main(){
	cin>>N;
	rep(i,N)cin>>h[i];
	rep(i,N)cin>>a[i];
	segm.init();
	rep(i,N){
		ll ma=segm.maxQ(0,h[i]+1);
		segm.add(h[i],ma+a[i]);
	}
	cout<<segm.maxQ(0,N+1)<<endl;
}

Measured memory_bytes: 8320
//#define M_PI 3.14159265358979323846
#define _USE_MATH_DEFINES

//#define _GLIBCXX_DEBUG
//#define all(x) (x).begin(),(x).end()

#include <bits/stdc++.h>

#define TASK ""
#define sqr(x) ((x)*(x))
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll INFLL = numeric_limits<int>::max();
const ll INFINT = numeric_limits<int>::max();
const ld EPS = 1e-7;
const ll MOD = 1000000000;
const ll MAXN = 123456;

void run()
{
    string s;
    cin >> s;
    for (int i = 0; i < (int) s.size() - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            cout << i + 1 << " " << i + 2;
            return;
        }
    }
    for (int i = 0; i < (int) s.size() - 2; i++)
    {
        if (s[i] == s[i + 2])
        {
            cout << i + 1 << " " << i + 3;
            return;
        }
    }
    cout << "-1 -1";
}

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

#ifdef LOCAL
//#define STRESS
#ifdef STRESS
    freopen("input.txt", "w", stdout);
    cout << "1000 50\n";
    for (int i = 0; i < 999; i++)
    {
        for (int j = 0; j < 999; j++) cout << ".";
        cout << "X\n";
    }
    for (int j = 0; j < 1000; j++)
        if (j != 1000 / 50)cout << "X";
        else cout << ".";
    return 0;

#endif
    if (strcmp(TASK, "-") != 0)
    {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#else
    if (strcmp(TASK, "")   != 0)
    {
        freopen(TASK".in", "r", stdin)  ;
        freopen(TASK".out", "w", stdout)  ;
    }
#endif
    run();

    return 0;
}

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

using namespace std;

const int N = 101;
const int W = 1e5 + 1;

using ll = long long;

int value[N], weight[N];
ll dp[N][W];

ll solve(int i, int j) {
    if (j < 0) {
        return -1e18;
    }
    if (i == 0) {
        return 0;
    }
    ll& ans = dp[i][j];
    if (ans != -1) {
        return ans;
    }
    ans = max(solve(i - 1, j), solve(i - 1, j - weight[i]) + value[i]);
    return ans;
}

int main() {
    int n, w;
    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    memset(dp, -1, sizeof dp);
    cout << solve(n, w);
    return 0;
}


Measured memory_bytes: 79104
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;


int main() {
    llong a, b, c;

    cin >> a >> b >> c;

    llong m = max({a, b, c});
    llong ans = (m - a) / 2 + (m - b) / 2 + (m - c) / 2;
    a += (m - a) / 2 * 2;
    b += (m - b) / 2 * 2;
    c += (m - c) / 2 * 2;

    if (abs(m - a) + abs(m - b) + abs(m - c) == 2) ans++;
    else if (abs(m - a) + abs(m - b) + abs(m - c) == 1)ans += 2;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <math.h>
#include <map>
#include <set>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll INF = 1000000000000000000LL;
using namespace std;

const int MOD = 1000000007;



int main(){
    int n;
    cin >> n;
    vector <int> p(n);
    vector <int> kai(n);
    //階段になっている数列(1,2,3,4)の最長な気がする
    //操作が「階段以外一気に取り出して、順番に入れ替える」と同義っぽい
    // kai[i] = iがなんばんめに登場するか
    REP(i,n)
    {
        cin >> p[i];
        --p[i];
        kai[p[i]] = i;
    }

    int ren_m = 0;
    int ren = 1;
    for(int i = 0; i < n-1; ++i)
    {
        if(kai[i] < kai[i+1])
        {
            ++ren;
        }
        else
        {
            ren_m = max(ren_m, ren);
            ren = 1;
        }
    }

    ren_m = max(ren_m, ren);

    int res;
    res = n - ren_m;
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  vector<int> v = {a,b,c,d};
  sort(all(v));
  if(v[0] == 1 && v[1] == 4 && v[2] == 7 && v[3] == 9) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 764
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 

void solve(){
	cout <<  fixed;
	cout << setprecision(10);
    double a, b , c;
    cin >> a >> b >> c;
    c = c / 180.0 * M_PI;
    double s = a * b * sin(c) / 2.0;
    double l =  sqrt(a*a+b*b-2*a*b*cos(c))+a+b;
    double h = b * sin(c);	
    cout << s << endl;
    cout << l << endl;
    cout << h << endl;
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



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

int main()
{
  string S;
  cin >> S;
  int N = S.size();
  int i = 0;
  int M = 0;
  // O(N)のアルゴリズム
  while (i < N)
  {
    int tmp = 0;
    while (1)
    {
      if (S.at(i) == 'A' || S.at(i) == 'C' || S.at(i) == 'G' || S.at(i) == 'T')
      {
        tmp++;
        i++;
        if (i == N)
        {
          break;
        }
      }
      else
      {
        break;
      }
    }
    M = max(M, tmp);
    i++;
  }
  cout << M << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <math.h>

typedef long long ll;

#define vi std::vector<int>
#define vl std::vector<ll>
#define floop(n) for(int i = 0; i < n; ++i)
#define print(x) std::cout << x << std::endl;

const ll INF = 1e18;

int main()
{
    int X;
    std::cin >> X;

    if(X >= 400 && X < 600)
    {
        print(8);
    }
    else if(X >= 600 && X < 800)
    {
        print(7);
    }
    else if(X >= 800 && X < 1000)
    {
        print(6);
    }
    else if(X >= 1000 && X < 1200)
    {
        print(5);
    }
    else if(X >= 1200 && X < 1400)
    {
        print(4);
    }
    else if(X >= 1400 && X < 1600)
    {
        print(3);
    }
    else if(X >= 1600 && X < 1800)
    {
        print(2);
    }
    else if(X >= 1800 && X < 2000)
    {
        print(1);
    }

    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
using namespace std; // 575

const int MOD = 1000000007; // 今回使う余り
int main() {
	int N;
	cin >> N;
	int dp[64][100];
	for (int i = 0;i < 64;++ i) dp[i][0] = 1;
	dp[6][0] = dp[9][0] = dp[33][0] = 0;
	for (int i = 1;i < N - 2;++ i) {
		for (int j = 0;j < 64;++ j) {
			dp[j][i] = 0;
			for (int k = 0;k < 4;++ k) dp[j][i] = (dp[j][i] + dp[j >> 2 | k << 4][i - 1]) % MOD;
		}
		for (int k = 0;k < 4;++ k) dp[33 | k << 2][i] = (dp[33 | k << 2][i] + MOD - dp[8 | k][i - 1]) % MOD;
		for (int k = 0;k < 4;++ k) dp[9 | k << 4][i] = (dp[9 | k << 4][i] + MOD - dp[2 | k << 2][i - 1]) % MOD;
		dp[41][i] = (dp[41][i] + dp[10][i - 1]) % MOD;
		dp[6][i] = dp[9][i] = dp[33][i] = 0;
	}
	int ans = 0;
	for (int i = 0;i < 64;++ i) ans = (ans + dp[i][N - 3]) % MOD;
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

1文字ずつ追加したときダメな遷移
?AG→AGC
?AC→ACG
?GA→GAC
AG?→G?C
A?G→?GC
なお重複はAGG→GGC
後は可能
*/

Measured memory_bytes: 384
n = gets.chomp.to_i
array = []

(n).times do |index| 
  command = gets.chomp.split
  case command[0]
  when 'insert'
    array.unshift command[1]
  when 'delete'
    found = false
    array.delete_if do |item|
      if item == command[1] then
        if !found then
          found = true
        end
      end
    end
  when 'deleteFirst'
    array.shift
  when 'deleteLast'
    array.pop
  end
end

puts array.join(' ')

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

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)

int main(){
    int n,m=0,ans=0;
    int h[25];
    sc1(n);
    rep(i,n) sc1(h[i]);
    rep(i,n) {
        if (h[i]>=m) {
            m=h[i];
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}


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


const int INF = 1e9+7;

int main(){
    long long n;
    cin>>n;
    
    long long arr[n],dp[n];
    
    memset(dp,INF,sizeof(dp));
    
    for(int i=0;i<n;i++)
        cin>>arr[i];
    
    dp[0]=0;
    
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=i+2;j++){
            if(j<n){
                dp[j]=min(dp[j],dp[i]+abs(arr[j]-arr[i]));
            }
        }
    }
    cout<<dp[n-1]<<endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string a,b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
{
    ・全探索できるなら全探索しろ
    ・異常な制約ならそこに注目
}
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'¥n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え('='でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
doubleを扱うときには(abs)ではなく'fabs'!!!
*/

Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int r;
    cin>>r;
    if(r<1200)cout<<"ABC"<<endl;
    else if(r<2800)cout<<"ARC"<<endl;
    else cout<<"AGC"<<endl;
}


Measured memory_bytes: 768
#line 1 "/workspaces/compro/lib/template.hpp"


#line 1 "/workspaces/compro/lib/io/vector.hpp"
#include <iostream>
#include <vector>

#ifndef IO_VECTOR
#define IO_VECTOR

template <class T> std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
  int size = v.size();
  for (int i = 0; i < size; i++) {
    std::cout << v[i];
    if (i != size - 1)
      std::cout << " ";
  }
  return out;
}

template <class T> std::istream &operator>>(std::istream &in, std::vector<T> &v) {
  for (auto &el : v) {
    std::cin >> el;
  }
  return in;
}

#endif
#line 4 "/workspaces/compro/lib/template.hpp"
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "main.cpp"

const std::string YES = "Yes";
const std::string NO = "No";
bool solve(long long X) { return 30 <= X; }

// generated by online-judge-template-generator v4.4.0 (https://github.com/kmyk/online-judge-template-generator)
int main() {
  long long X;
  std::cin >> X;
  auto ans = solve(X);
  std::cout << (ans ? YES : NO) << std::endl;
  return 0;
}


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

int main() {
    int64_t x, y;
    cin >> x >> y;

    bool r = (x < 2 && y < 2) || abs(x - y) <= 1;
    cout << (!r ? "Alice" : "Brown") << endl;

    return 0;
}

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

int main(){
  int N,a;
  cin >> N;
  
  for(int i = 0; i < N; i++){
    int x,y;
    cin >> x >> y;
    
    a += (y+1) - x;
  }
  
  cout << a << endl;
}

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

struct NODE{
	int x,y,a,b,cost;
	NODE(int A,int B,int C,int D,int E){
		x = A , 
		y = B , 
		a = C , 
		b = D , 
		cost = E ;
	}
};

int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};
char dc[]= {'L','U','R','D'};
int main(){
	int W,H;
	while(cin >> H >> W , H ){
		char field[52][52];
		rep(i,52)rep(j,52)field[i][j] = '#';
		rep(i,H)rep(j,W)cin >> field[i+1][j+1];
		int sx , sy;
		rep(i,H+1)rep(j,W+1)
			if(field[i][j] == 'S') sx = j , sy = i;
		int p;
		cin >> p;
		vector<string> P(10);
		rep(i,p) cin >> P[i];
		//rep(i,p)rep(j,p-1)if(P[j].length() < P[j+1].length() ) swap(P[j],P[j+1]);
		
		
		bool done[52][52][11][11]={0};
		queue<NODE> Q;
		Q.push(NODE(sx,sy,0,0,0));
		//rep(i,p)cout << P[i] << endl;
		while(Q.size()){
			NODE q = Q.front(); Q.pop();
			string pt = P[q.a].substr(0,q.b);
			bool f = true;
			rep(i,p) if(~pt.find(P[i]))f=0;
			if(!f)continue;
			if(field[q.y][q.x] == 'G'){
				cout << q.cost << endl;
				goto end;
			}
			
			if(done[q.y][q.x][q.a][q.b]) continue;
			else done[q.y][q.x][q.a][q.b] = true;
			
			if(field[q.y][q.x] == '#') continue;
			
			rep(d,4){
				string st , t = pt + dc[d];
				int tx = q.x + dx[d] , ty = q.y + dy[d];
				rep(i,t.size()){
					st = t.substr(i);
					rep(j,p){
						if( P[j].find(st) == 0){
							Q.push(NODE(q.x+dx[d],q.y+dy[d],j,st.size(),q.cost+1));
							goto ooo;
						}
					}
				}
				Q.push(NODE(q.x+dx[d],q.y+dy[d],0,0,q.cost+1));
				ooo:;
				
			}
		}
		cout << -1 << endl;
		end:;
	}	
}

Measured memory_bytes: 1420
h, w = list(map(int, input().split()))
grid = [input() for _ in range(h)]

x = 0
y = 0

while True:
    c = []
    neighbours = 0
    if x != w-1:
        c.append([x+1, y, 1])
    if y != h-1:
        c.append([x, y+1, 3])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1
            x2 = coords[0]
            y2 = coords[1]

    if neighbours != 1 and not (x == w-1 and y == h-1):
        print("Impossible")
        break

    c = []
    neighbours = 0
    if x != 0:
        c.append([x-1, y, 0])
    if y != 0:
        c.append([x, y-1, 2])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1

    if neighbours > 1:
        print("Impossible")
        break

    if x == w-1 and y == h-1:
        print("Possible")
        break

    x = x2
    y = y2

Measured memory_bytes: 9032
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int a[N],ans;
  for(int i = 0;i < N; i++){
    cin >> a[i];
    ans = ans + a[i] - 1;
  }
  cout << ans << endl;
  return 0;
}
  

Measured memory_bytes: 256
//Crane and Turtle

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using p = pair<ll, string>;
using garph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int x,y;cin>>x>>y;
    rep(i,0,x+1){
        if(i*2+(x-i)*4==y){
            cout<<"Yes"<<nnn;
            return 0;
        }
    }
    cout<<"No"<<nnn;
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<climits>
#include<set>
#include<utility>
using namespace std;
typedef long long int ll;

int main(){

	ll n, a[100000], ans=0, sum=0, tmp;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
		sum+=a[i];
		if(i%2==0 && sum<=0){
			ans+=abs(sum);
			ans++;
			sum=1;
		}
		if(i%2!=0 && sum>=0){
			ans+=sum;
			ans++;
			sum=-1;
		}
	}
	tmp=ans;
	ans=0;
	sum=0;
	for(int i=0; i<n; i++){
		sum+=a[i];
		if(i%2==0 && sum>=0){
			ans+=sum;
			ans++;
			sum=-1;
		}
		if(i%2!=0 && sum<=0){
			ans+=abs(sum);
			ans++;
			sum=1;
		}
	}
	cout << min(tmp, ans) << endl;

	return 0;
}

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

int main(){
  string s;
  cin >> s;
  int ans = 10000000;
  rep(j, 2){
    int count = 0;
    char pre = 'a';
    rep(i, s.length()){
      if(s[i] != pre){
        count++;
        pre = s[i];
      }
    }
    ans = min(ans, count);
    reverse(s.begin(), s.end());
  }
  ans--;

  cout << ans << endl;
  
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
ll INF = (1 << 30);
ll MOD = 1e9 + 7;

vector<int> par;
vector<int> RANK;
void init(int n){
    for(int i = 0; i < n; i++){
        par.pb(i);
        RANK.pb(0);
    }return;
}

int FindRoot(int x){
    if(par[x] == x) return x;
    par[x] = FindRoot(par[x]);
    return par[x];
}

bool isSame(int x, int y){
    return FindRoot(x) == FindRoot(y);
}

void Union(int x, int y) {
    x = FindRoot(x);
    y = FindRoot(y);
    if (x == y) return;
    if (RANK[x] > RANK[y]) par[y] = x;
    else {
        par[x] = y;
        if (RANK[x] == RANK[y]) {
            RANK[y]++;
        }
    }
    return;
}

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

    init(n);

    vector<vector<int>> Friend(n);
    vector<int> block(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        Friend[a].pb(b);
        Friend[b].pb(a);
        Union(a,b);
    }
    for(int i = 0; i < k; i++){
        int c, d; cin >> c >> d;
        c--; d--;
        if(isSame(c,d)) {
            block[c]++;
            block[d]++;
        }
    }
    //それぞれの木のサイズを格納する
    vector<int> kisize(n);
    for(int i = 0; i < n; i++){
        int v = FindRoot(i);
        kisize[v]++;
    }

    for(int i = 0; i < n; ++i){
        int v = FindRoot(i);
        cout << kisize[v] - Friend[i].size() - block[i] - 1 << " ";
    }
}

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

int main(){
  string mables;
  cin>>mables;
  
  int counter = 0;
  for(int i = 0; i < mables.size(); i++){
    if(mables.at(i) == '1'){
      counter++;
    }
  }
  cout<<counter<<"\n";
}

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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N = 1e5 + 3;
ll dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    int n,c,w,v; cin >> n >> c;
    ll ans = 0;

    for(int i = 0; i < n; i++) {
        cin >> w >> v;
        for(int j = c; j-w >= 0; j--) {
            dp[j] = max(dp[j], dp[j-w] + v);
            ans = max(ans,dp[j]);
        }
    }

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


Measured memory_bytes: 1024
import java.math.BigInteger;
import java.util.*;
import java.util.stream.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt(), m = scanner.nextInt(), gcd = BigInteger.valueOf(n).gcd(BigInteger.valueOf(m)).intValue();
        String s = scanner.next(), t = scanner.next();
        System.out.println(IntStream.range(0, gcd).filter(k -> s.charAt(k * n / gcd) != t.charAt(k * m / gcd)).mapToLong(k -> -1).findAny().orElse(BigInteger.valueOf(n).multiply(BigInteger.valueOf(m)).divide(BigInteger.valueOf(gcd)).longValue()));
    }
}

Measured memory_bytes: 30500