akhauriyash/Code-Regression huggingface dataset:
use either::*;
use proconio::input;
use proconio::marker::{Chars, Usize1};

fn main() {
    input! {
        n: usize,
        mut s: Chars,
        q: usize,
    }
    let mut queries: Vec<(usize, usize, Either<usize, char>)> = vec![];
    for _ in 0..q {
        input! {
            k: usize,
        }
        if k == 1 {
            input! {
                i: Usize1,
                c: char,
            }
            queries.push((k, i, Right(c)))
        } else if k == 2 {
            input! {
                l: Usize1,
                r: Usize1,
            }
            queries.push((k, l, Left(r)));
        }
    }

    let mut bits: Vec<BIT<isize>> = vec![BIT::new(n); 26];
    for i in 0u8..26 {
        let c = ('a' as u8 + i) as char;
        for (i, ns) in s.iter().enumerate() {
            if *ns == c {
                let index = (*ns as u8 - 'a' as u8) as usize;
                bits[index].add(i, 1);
            }
        }
    }

    for &query in &queries {
        if query.0 == 1 {
            update_bits(&mut s, &mut bits, query.1, query.2.right().unwrap());
        } else if query.0 == 2 {
            let ans = calc(&bits, query.1, query.2.left().unwrap());
            println!("{}", ans);
        }
    }
}

fn update_bits(s: &mut Vec<char>, bits: &mut Vec<BIT<isize>>, from: usize, to: char) {
    let c = (s[from] as u8 - 'a' as u8) as usize;
    bits[c].add(from, -1);
    let index = (to as u8 - 'a' as u8) as usize;
    bits[index].add(from, 1);
    s[from] = to;
}

fn calc(bits: &Vec<BIT<isize>>, l: usize, r: usize) -> usize {
    //println!("l {}, r {}", l, r);
    let mut count = 0;
    for bit in bits {
        if bit.sum(l as isize, (r + 1) as isize) != 0 {
            count += 1;
        }
    }
    count
}

use num::Num;

#[derive(Clone)]
struct BIT<T> {
    pub n: usize,
    pub d: Vec<T>,
}

impl<T> BIT<T>
where
    T: Num + Copy + Clone,
{
    fn new(n: usize) -> Self {
        BIT {
            n: n,
            d: vec![T::zero(); n + 1],
        }
    }

    fn add(&mut self, mut i: usize, x: T) {
        i += 1;
        while i <= self.n {
            self.d[i] = self.d[i] + x;
            i += i & i.wrapping_neg();
        }
    }

    fn sum_one(&self, mut i: isize) -> T {
        if i < 0 {
            return T::zero();
        }
        let mut x = T::zero();
        i += 1;
        while i != 0 {
            x = x + self.d[i as usize];
            i -= i & i.wrapping_neg();
        }
        x
    }

    fn sum(&self, l: isize, r: isize) -> T {
        self.sum_one(r - 1) - self.sum_one(l - 1)
    }
}


Measured memory_bytes: 107088
n = int(input())
p = list(map(int, input().split()))

count = 0
for i in range(1, n - 1):
    if p[i-1] < p[i] < p[i + 1] or p[i - 1] > p[i] > p[i + 1]:
        count += 1

print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){cerr << name << " : " << arg1 << '\n';}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}

const ll inf = 1e18 + 1;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

int main() {
	double t;
	cin>>t;
	cout<<ceil(t/2)<<"\n";
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> b(n), c(n);
    b[0] = a[0];
    rep(i, n - 1) b[i + 1] = gcd(b[i], a[i + 1]);
    c[n - 1] = a[n - 1];
    repr(i, n - 2) c[i] = gcd(c[i + 1], a[i]);
    int ans = 0;
    rep(i, n)
    {
        int num1 = (i > 0 ? b[i - 1] : -1), num2 = (i + 1 < n ? c[i + 1] : -1);
        if (num1 == -1)
            ans = max(ans, num2);
        else if (num2 == -1)
            ans = max(ans, num1);
        else
            ans = max(ans, gcd(num1, num2));
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
# 始点と終点を全て格納する
X = [[0]*501 for _ in range(501)]
# 累積和を取るための二次元リスト(累積和自体は一次元, 最後に縦方向に和を取る)
C = [[0]*501 for _ in range(501)]

for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1  # 始点と終点を全て格納する

# 横方向に累積和を取る
for i in range(N):
    for j in range(N):
        C[i][j] = C[i][j-1] + X[i][j]

for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)


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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();
		
		if ((b - a) < 2 * k) {
			for (int i = a; i <= b; i++) {
				System.out.println(i);
			}
		} else {
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < k; i++) {
				list.add(a + i);
				list.add(b - i);
			}
			Collections.sort(list);
			for (int i = 0; i < list.size(); i++) {
				System.out.println(list.get(i));
			}
		}
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	string t="keyence";
	int i=0;
	while(s[i++]==t[0]&&!t.empty())t=t.substr(1);
	i=s.size()-1;
	while(s[i--]==t[t.size()-1]&&!t.empty())t=t.substr(0,t.size()-1);
	if(!t.size())
		cout<<"YES";
	else
		cout<<"NO";
}

Measured memory_bytes: 256
#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 <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

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

    map<ll, ll> even, odd;
    vector<ll> v(n);

    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        if (i & 1)
        {
            odd[v[i]]++;
        }
        else
        {
            even[v[i]]++;
        }
    }

    priority_queue<P> eq, oq;

    eq.push({0, 0});
    oq.push({0, 0});

    for (auto x : even)
    {
        eq.push({x.second, x.first});
    }

    for (auto x : odd)
    {
        oq.push({x.second, x.first});
    }

    if (eq.top().second != oq.top().second)
    {
        cout << n - eq.top().first - oq.top().first << endl;

        return 0;
    }
    else
    {
        P e1, e2, o1, o2;
        e1 = eq.top();
        eq.pop();
        o1 = oq.top();
        oq.pop();

        e2 = eq.top();
        o2 = oq.top();

        cout << n - max(e1.first + o2.first, e2.first + o1.first) << endl;
    }
}

Measured memory_bytes: 9592
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

void primeFactor(int n, map<int,int>& m){
	for(int i = 2; i * i <= n; i++){
		while(n % i == 0){
			++m[i];
			n /= i;
		}
	}
	if(n != 1) m[n] += 1;
}

int dp(vector<int>& e, int x = 75){
	vector<vector<int>> dp(e.size() + 1, vector<int>(x + 1,0));
	dp[0][1] = 1;
	rep(i,e.size()){
		range(j,1,x + 1){
			rep(k,e[i] + 1){
				if(j * (k + 1) > x) break;
				dp[i + 1][j * (k + 1)] += dp[i][j];
			}
		}
		//rep(j,dp.size()){
		//	rep(k,dp[0].size()){
		//		cout << dp[j][k] << ' ';
		//	}
		//	cout << endl;
		//}
		//	cout << endl;
	}
	return dp[e.size()][x];
}

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

	map<int,int> m;
	range(i,1,n + 1){
		primeFactor(i,m);
	}

	vector<int> v;
	for(auto i : m){
		v.emplace_back(i.second);
	}
	cout << dp(v) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <bits/stdc++.h>
#include <set>
#include <list> //list<???> a; a.push_back ,insert(追加したい要素),a.sort(),参照できない
#include <vector> //vector<???> a; a.push_back,sort(a.begin(),a.end());a[i]
//配列 int a[N];a[i]=追加したい要素;sort(a,a+N);a[i]
const int MOD = 1e9+7;
using namespace std;
typedef long  ll;
#define rep(i,n) for(int i=0;i<(n);i++)


//using namespace std;
//


int main(){
  string moji;cin>>moji;
  int cnt=0,ans=0;
  int flag=1;
  for(int i=0;i<moji.size();i++){
    if(flag==0){
      break;
    }

    if(moji[i]=='A'){
      for(int j=moji.size()-1;0<=j;j--){
        if(moji[j]=='Z'){
          cout<<j-i+1<<endl;
          flag=0;
          break;
        }
      }
    }
  }
}


Measured memory_bytes: 640
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    ArrayList<Integer> list = new ArrayList<Integer>();
	  int all = scan.nextInt();
    int extraction  = scan.nextInt();
    int b=0;
    for(int i = 0; i<all;i++){
      b=scan.nextInt();
      list.add(b);
    }
    Collections.sort(list);
    int ans=2147483647;
    for(int i = 0;i<(all-extraction+1);i++){
      if(ans>list.get(i+extraction-1)-list.get(i)) ans = list.get(i+extraction-1)-list.get(i);
      // System.out.println("今は"+list.get(i+extraction-1));
      // System.out.println("今は2回目"+list.get(i));
    }
    System.out.println(ans);
}
}


Measured memory_bytes: 62400
fun main(args: Array<String>) {
    a96(readLineList())
}

fun readLineList(): Array<String> {
    val lineList = mutableListOf<String>()
    while (true) {
        val line = readLine()
        if (line.isNullOrBlank()) {
            break
        } else {
            lineList.add(line!!)
        }
    }
    return lineList.toTypedArray()
}

fun a96(args: Array<String>) {
    if (args.size != 1) {
        throw IllegalArgumentException()
    }
    val (month, day) = args[0].split(" ").map { it.toInt() }
    println(if (month > day) month - 1 else month)
}

Measured memory_bytes: 38172
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb push_back;
#define sp " ";
#define INF=200000000;
void vout(vector<int> v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
vi par(1000000);/*親*/
vi hukasa(1000000);/*根の深さ*/
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        hukasa[i]=0;
    }
}
/*木の根を求める*/
int find(int x){
    if(par[x]==x){/*親が自分自身＝根*/
        return x;
    }
    else{
        return par[x]=find(par[x]);/*一つ上の階層へ*/
    }
}
/*ｘとｙの集合を併合*/
void unite(int x,int y){
    x=find(x);
    y=find(y);
    /*根を求める*/
    if(x==y) return;/*同じ集合に属していたら終了*/
    if(hukasa[x]<hukasa[y]){
        par[x]=y;
    }
    else{
        par[y]=x;
        if(hukasa[x]=hukasa[y]) hukasa[x]++;
    }
}
/*同じ集合に属するか調べる*/
bool same(int x,int y){
    return find(x)==find(y);
}
/*利用方法はparのそれぞれの要素に対応させる形で別の配列を用意し、そこに入力する。*/
int main(){
    int n,m;
    cin>>n>>m;
    init(n);
    rep(i,m){
        int x,y,z;
        cin>>x>>y>>z;
        x--;y--;
        unite(x,y);
    }
    set<int> p;
    rep(i,n){
        if(!p.count(find(i))){
            p.insert(find(i));
        }
    }
    cout<<p.size();

}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = (int)1e9 + 7;
const int INF = (int)100100100;

int main() {
    ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    string a,b,c;
    cin >> a >> b >> c;
    ll sum=0;
    for(int i=0;i<N;i++){
        if(a[i]!=b[i])sum++;
        if(a[i]!=c[i] && b[i]!=c[i])sum++;
    }
    cout << sum << endl;
    


}

/*



 */



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


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

	string ans = "No";
	if ((a < c && c < b) || (b < c && c < a)) {
		ans = "Yes";
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

ans = 0
n.times do |i|
  ans += b[a[i] - 1]
  ans += c[a[i - 1] - 1] if i != 0 && a[i] == a[i - 1] + 1
end
puts ans


Measured memory_bytes: 1788
#include <iostream>
using namespace std;
int main(void){
    int n, i, b, f, r, v, HOUSE[5][4][11]={};
    
    cin >> n;
    for(i=0; i<n; i++){
        cin >> b >> f >> r >> v;
        HOUSE[b][f][r] += v;
    }
    
    for(b=1; b<=4; b++){
        for(f=1; f<=3; f++){
            for(r=1; r<=10; r++){
                cout << " " << HOUSE[b][f][r];
            }
            if(r != 10 || b != 4 || f != 3) cout << endl;
        }
        if(b != 4) cout << "####################" << endl;
    }
    return 0;
}



Measured memory_bytes: 3056
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans = a*c;
  if(ans < a*d) ans = (ll)a*d;
  if(ans < b*c) ans = (ll)b*c;
  if(ans < b*d) ans = (ll)b*d;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  int ans = 0;
  FOR(i, 0, N)
  {
    int in;
    cin >> in;
    ans += min(in, K - in) * 2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, 0, n) cin >> a[i];

  ll sum_val = accumulate(a.begin(), a.end(), 0);
  cout << sum_val - n << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
  int N,i;
  scanf("%d\n",&N);
  int A[N];
  i = 0;
  while (i < N)
  {
    scanf("%d ",&A[i]);
    if (A[i] % 2 == 0)
    {
      if (!(A[i] % 3 == 0 || A[i] % 5 == 0))
      {
        printf("DENIED");
        return (0);
      }
    }
    i++;
  }
  printf("APPROVED");
}

Measured memory_bytes: 128
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto nx = readln.split.to!(long[]);
    auto N = nx[0];
    auto X = nx[1];
    auto xs = readln.split.to!(long[]);
    auto r = abs(xs[0] - X);
    foreach (x; xs[1..$]) {
        r = gcd(r, abs(x - X));
    }
    writeln(r);
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int N; cin >> N;
  int K; cin >> K;
  vector<ll> A(N); REP(i, N) cin >> A[i];
  // 判定パート
  for(int i = K; i < N; ++i) {
    if(A[i] > A[i - K]) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 4836
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pull = pair<ull, ll>;
using pis = pair<int, string>;
#define all(x) (x).begin(), (x).end()
#define INF 1000000000
#define LLINF 10000000000000000ll
#define MOD 1000000007ll

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(15)
  ll n;
  cin >> n;
  ll ans = 0;
  for (int i = 1; i < n; i++) {
    ans += ((n-1) / i);
  }
  cout << ans << endl;
}



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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
template<class T> inline bool chmax(T& a,T b){ if(a<b){a=b;return 1;}return 0; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){a=b;return 1;}return 0; }
//end

bool f[201000]={};

int main(){
   int n,k,c; cin>>n>>k>>c;
   string s; cin>>s; int sum=0;
   rep(i,0,n)if(s[n-1-i]=='o'){
      sum++; f[n-1-i]=1; i+=c;
   }
   if(sum>k)return 0;
   rep(i,0,s.size())if(s[i]=='o'){
      if(f[i])cout<<i+1<<endl;
      i+=c;
   }
   return 0;
}

Measured memory_bytes: 2052
#include<stdio.h>
#include<string.h>
int main(void)
{
	int cnt,flg[101],x=0,i,j;
	char a[101];
	scanf("%s",a);
	for(i=0;i<strlen(a);i++){
		flg[i]=0;
	}
	for(i=0;i<strlen(a);i++){
		if(flg[i]==0){
			cnt=0;
			for(j=i;j<strlen(a);j++){
				if(a[i]==a[j]){
					cnt++;
					flg[j]=1;
				}
			}
		}
		if(cnt%2!=0){
			x=1;
			break;
		}
	}
	if(x==0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
	string str;
	cin >> str;
	int s = 0, n = 0, w = 0, e = 0;
	for (int unsigned i = 0; i < str.size(); i++) {
		if (str[i] == 'S') s++;
		if (str[i] == 'N') n++;
		if (str[i] == 'W') w++;
		if (str[i] == 'E') e++;
	}
	if (((s>0&&n>0)||(s==0&&n==0)) && ((w>0&&e>0)||(w==0&&e==0))) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import sys
import math
import bisect

def main():
    a, b = map(int, input().split())
    ans = 0
    if a >= b:
        ans += a
        a -= 1
    else:
        ans += b
        b -= 1
    if a >= b:
        ans += a
        a -= 1
    else:
        ans += b
        b -= 1
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
S = input()

if S == 'RSS' or S == 'SRS' or S == 'SSR' or S == 'RSR':
    print(1)
elif S == 'RRS' or S == 'SRR':
    print(2)
elif S == 'RRR':
    print(3)
else:
    print(0)

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

using namespace std;

int a[100005],b[100005];
int jue(int a)
{
    if(a<0)
    {
        return -a;
    }
    else
    {
        return a;
    }
}
int main()
{
    int n,i,z,w;
    scanf("%d %d %d",&n,&z,&w);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    if(n==1)
    {
        printf("%d\n",jue(a[n]-w));
    }
    else
    {
        printf("%d\n",max(jue(a[n-1]-a[n]),jue(a[n]-w)));
    }
    return 0;
}


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

using namespace std;

typedef long long ll;

const int N = 1000;
ll A[N], B[N], C[N];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int x, y, z, want;
	cin >> x >> y >> z >> want;
	for(int i = 0; i < x; i++)
		cin >> A[i];
	for(int i = 0; i < y; i++)
		cin >> B[i];
	for(int i = 0; i < z; i++)
		cin >> C[i];
	sort(C, C + z);
	priority_queue<pair<ll, pair<int, pair<int, int>>>> pq;
	for(int i = 0; i < x; i++)
		for(int j = 0; j < y; j++)
			pq.push({A[i] + B[j] + C[z - 1], {i, {j, z - 1}}});
	while(want)
	{
		cout << pq.top().first << '\n';
		int i = pq.top().second.first;
		int j = pq.top().second.second.first;
		int k = pq.top().second.second.second;
		pq.pop();
		if(k)
			pq.push({A[i] + B[j] + C[k - 1], {i, {j, k - 1}}});
		want--;
	}
	return 0;
}


Measured memory_bytes: 26984
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define PII pair<int,int>
#define MP make_pair
#define PB push_back
typedef long long LL;
const LL P = 998244353;
const int N = 200010;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int k,x;

int main(){
	cin>>k>>x;
	rep(i,x-k+1,x+k-1)cout<<i<<" ";cout<<endl;
	return 0;
}

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

using namespace std;

const long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}

int arr[100001];

int main(){

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;

    long long tot = 1;

    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        arr[a]++;
        if(i % 2 == 1){
            tot = tot * 2 % MOD;
        }
    }

    for(int i = 0; i < n; ++i){
        if(arr[i] == 2){
            if(i & 1 == n & 1){
                tot *= 0;
                break;
            }
        } else if(arr[i] == 1){
            if(i != 0){
                tot *= 0;
                break;
            }
        }
    }

    cout << tot;


    return 0;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

//global variance
int N;
int result = 0;
int A[100];
int B[100];

//prototype
void nhap(int arr[], int & N);

int main()
{
    nhap(B, N);
    for(int i = 0; i < N-1; ++i)
    {
       A[i] = A[i+1] = B[i];
       if (A[i] > B[i-1] && i != 0) A[i] = B[i-1]; 
    }//cout << A[0] << A[1] << A[2] << endl;
    for(int i = 0; i < N; ++i)
    {
        result += A[i];
    }

    cout << result;
    return 0;
}
//definition
void nhap(int arr[], int & N)
{
    cin >> N;
    for(int i = 0; i < N-1; ++i)
    {
        cin >> B[i];
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
cin>>N;
int A[110];
for(int i=0; i<N; ++i) cin>>A[i];
sort(A, A+N, greater<int>());
int sum=0;
for(int i=1; i<N; ++i)
{
sum+=A[i];
}
if(A[0]<sum){
cout<<"Yes"<<endl;
}else
cout<<"No"<<endl;
}


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

#define whole(f, x, ...)                                 \
  ([&](decltype((x)) whole) {                            \
    return (f)(begin(whole), end(whole), ##__VA_ARGS__); \
  })(x)

using namespace std;
using ll = long long;

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

void solve() {
  int n;
  cin >> n;
  vector<pair<ll, int>> a(n);
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    a[i] = {x, i};
  }
  sort(a.begin(), a.end(), greater<>());

  vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
  for (int x = 0; x < n; x++) {
    for (int y = 0; x + y < n; y++) {
      chmax(dp[x + 1][y], dp[x][y] + a[x + y].first * abs(a[x + y].second - x));
      chmax(dp[x][y + 1],
            dp[x][y] + a[x + y].first * abs(a[x + y].second - (n - y - 1)));
    }
  }
  ll ma = 0;
  for (int i = 0; i < n; i++) {
    chmax(ma, dp[i][n - i]);
  }
  cout << ma << endl;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);

  solve();
  return 0;
}


Measured memory_bytes: 34620
X = int(input())

#A**5,B**5でとり得る可能性のある数をあらかじめリストで用意する

N = [i**5 for i in range(1000)]
 
#A,Bで別々の数を扱うので、変数はi,jの２種を用意する

for i in range(1000):
	for j in range(1000):

#リストから２つの数を抽出し、Xになるか計算を繰り返す
#Xは正の整数であるため、Aが負になる可能性は除外

		if N[j] - N[i] == X:
			print(j, i)
			exit()

#Bが負の場合、符号が変わる可能性があるため、もう１パターン計算

		if N[j] + N[i] == X:
			print(j, -i)
			exit()

Measured memory_bytes: 9196
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

a = ["#"*(W+2)] + ["#"+input()+"#" for _ in range(H)] + ["#"*(W+2)]
print(*["".join(x) for x in a], sep="\n")


Measured memory_bytes: 3896
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int h = in.nextInt();
            int w = in.nextInt();
            int k = in.nextInt() - 1;

            long MOD = 1000000007;

            long[] fibo = {1, 1, 2, 3, 5, 8, 13, 21};

            long[][] dp = new long[h + 1][w];
            dp[0][0] = 1;
            for (int i = 1; i <= h; i++) {
                for (int j = 0; j < w; j++) {
                    dp[i][j] = dp[i - 1][j] * fibo[j] * fibo[w - 1 - j] % MOD;
                    if (j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * fibo[j - 1] * fibo[w - 1 - j]) % MOD;
                    if (j < w - 1) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1] * fibo[j] * fibo[w - 2 - j]) % MOD;
                }
            }

            out.println(dp[h][k]);
        }

    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
            st = new StringTokenizer("");
        }

        public String nextString() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}



Measured memory_bytes: 21972
fun main(array: Array<String>) {
    var max = 0
    var idx = 0
    var ans = 0
    var list = mutableListOf<Int>()
    repeat(5) {
        //入力
        var num = readLine()!!.toInt()
        list.add(num)
        //差の最大値計算
        if(num % 10 != 0) {
            if(max <= 10 - num % 10) {
                max = 10 - num % 10
                idx = it
            }
        }
    }
    repeat(5) {
        if(it != idx) {
            ans += list[it]
            if(ans % 10 != 0) ans += 10 - ans % 10
        }
    }
    ans += list[idx]
    print(ans)
}

Measured memory_bytes: 33436
o=input()
e=input()
len_o,len_e=len(o),len(e)
ans=""
for i in range(len_o-1):
    ans+=(o[i]+e[i])
if len_o==len_e:
    ans+=(o[len_o-1]+e[len_e-1])
else:
    ans+=(o[len_o-1])
print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, s, t) for(i = s; i <= t; ++i)

using namespace std;

const int N = 1e5+10;
int n;
int t[N], x[N], y[N];

int main() {
	int i;
	scanf("%d", &n);
	rep(i, 1, n) scanf("%d %d %d", &t[i], &x[i], &y[i]);
	rep(i, 1, n) {
		if(t[i] - t[i-1] < abs(x[i]-x[i-1]) + abs(y[i]-y[i-1])) {puts("No"); return 0;}
		if((t[i]-t[i-1] & 1) != (abs(x[i]-x[i-1])+abs(y[i]-y[i-1]) & 1)) {puts("No"); return 0;}
	}
	puts("Yes");
	return 0;
} 

Measured memory_bytes: 1280
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

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

ll GCD(ll x, ll y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }

    if (a.second != b.second) {
        return a.second > b.second;
    }
    else {
        return true;
    }
}

int main()
{
  int N,X,S=0;
  cin >> N >> X;

  vector<int> m(N);

  rep(i,N) cin>>m[i];

  rep(i,N) S+=m[i];

  int T=X;

  rep(i,N) T=min(m[i],T);

  X-=S;

  cout << N+X/T << endl;
}

Measured memory_bytes: 256
from functools import reduce
from operator import mul
import math

def main():
    n = int(input())
    l = list(map(int, input().split()))

    if 0 in l:
        print(0)
        return
    l_sorted = sorted(l, reverse=True)
    log = 0
    seki = 1
    for i in l_sorted:
        log += math.log10(i)
        if log > 18:
            print(-1)
            return
        elif log == 18:
            seki *= i
            if seki != 10 ** 18:
                print(-1)
                return
        else:
            seki *= i
    print(seki)
    return


if __name__ == '__main__':
    main()

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

int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	vector<double> b(n);
	double ans = 0;
	rep(i, n){
		a.at(i) = i+1;
		b.at(i) = n;
		while(a.at(i) < k){
			a.at(i) *= 2;
			b.at(i) *= 2;
		}
		ans += 1/b.at(i);
	}
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

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

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    ll n;
    string s;
    cin>>s; n=s.size();
    int p=n-(n+1)/2;
    int tp=0;
    rep(i,0,n){
       if(s[i]=='p')tp++;
    }
    cout<<p-tp<<endl;
    return 0;
}




Measured memory_bytes: 512
#include <stdio.h>

int N;
int a[114514];

int main(void) {
	int i;
	int saisyou, saidai;
	int fuku_count;
	int tan_bousi, fuku_bousi;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &a[i]) != 1) return 1;
	}

	saisyou = saidai = a[0];
	for (i = 1; i < N; i++) {
		if (a[i] < saisyou) saisyou = a[i];
		if (a[i] > saidai) saidai = a[i];
	}
	if (saidai - saisyou > 1) {
		puts("No");
		return 0;
	}
	if (saidai == saisyou && saidai == N - 1) {
		puts("Yes");
		return 0;
	}

	fuku_count = 0;
	for (i = 0; i < N; i++) {
		if (a[i] == saidai) fuku_count++;
	}

	tan_bousi = N - fuku_count;
	fuku_bousi = saidai - tan_bousi;
	if (tan_bousi < 0 || fuku_bousi < 0) {
		puts("No");
		return 0;
	}
	if (saisyou != saidai && fuku_bousi == 0) {
		puts("No");
		return 0;
	}
	puts(fuku_count >= fuku_bousi * 2 ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 2044
import java.util.*;
import static java.lang.Math.*;
import java.io.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		while(sc.hasNextInt()) {
			int a=sc.nextInt(),b=sc.nextInt(),n=sc.nextInt(),ans=0;
			double count=(double)a/b;
			count-=Math.floor(count);
			String d=String.valueOf(count);
			for(int i=2;i<n+2;i++) {
				if(i>=d.length())break;
				String temp=String.valueOf(d.charAt(i));
				ans+=Integer.parseInt(temp);
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 20252
#include<bits/stdc++.h>
using namespace std;
 
template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}
 
template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
	in >> p.first >> p.second;
	return in;
}
 
template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
	for (T &x : v)
		in >> x;
	return in;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<vector<T> > &v)
{
	for (const vector<T> &x : v)
		out << x << '\n';
	return out;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
	for (const T &x : v)
		out << x << ' ';
	return out;
}
 
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll > ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define sz(x) (ll)(x).size()
#define tr1(x) cerr << #x << ": " << x << nl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << nl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<nl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<nl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<sz(a);zz++) cerr<<a[zz]<<" ";cerr<<nl
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<nl
#define epsilon 0.000000001L
#define inf 9999999999999999ll// ~ 10^16
#define nl endl
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define fast()  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mod 1000000007ll
#define modulo 998244353ll
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
 

int main() 
{
    fast();
    ll n;
    cin>>n;
    ll up = 1000*((999+n)/1000);
    cout<<up-n<<nl;
}


Measured memory_bytes: 3640
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const ll INF = 1e9+7;


int main(){
	ios_base::sync_with_stdio(false);
	int N;

	cin >> N;

	int sum = (N%2 ? N : N+1);

	vector<pii> ans;
	rep(i,N) reps(j,i+1,N) if( i + j + 2 != sum ) ans.emplace_back(i+1, j+1);

	cout << ans.size() << endl;
	for(auto p: ans) cout << p.X << " " << p.Y << endl;

	return 0;
}

Measured memory_bytes: 764
a = int(input())
b = int(input())
c = int(input())
pur = int(input())
n = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if (500*i + 100*j + 50*k) == pur:
        n = n + 1
print(n)

Measured memory_bytes: 3060
// Author: getharshkumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
pair<ll, ll> a[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, m;
    cin >> n >> m;
    for (ll i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;
    sort(a, a + n);
    priority_queue<ll> pq;
    ll s = 0;
    for (ll i = 1, j = 0; i <= m; i++)
    {
        while (a[j].first <= i && j < n)
            pq.push(a[j].second), j++;
        if (pq.size())
            s += pq.top(), pq.pop();
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 2936
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    dp0, dp1, dp2 = 0, 0, 0
    for _ in range(n):
        a, b, c = map(int, input().split())
        dp0, dp1, dp2 = max(dp1, dp2) + a, max(dp2, dp0) + b, max(dp0, dp1) + c
    print(max(dp0, dp1, dp2))
resolve()

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri();
	int res = 0;
	for (int i = 0; i < n; i++) {
		int x = ri();
		if (x == res + 1) res++;
	}
	std::cout << (!res ? -1 : n - res) << std::endl;
	return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[100005],q[100005],h[100005],ans;
int main()
{
	scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	q[1]=a[1];h[n]=a[n];
	for(int i=2;i<=n;++i) q[i]=__gcd(q[i-1],a[i]);
	for(int i=n-1;i;--i) h[i]=__gcd(h[i+1],a[i]);
	ans=max(ans,q[n-1]);
	ans=max(ans,h[2]);
	for(int i=2;i<=n-1;++i) ans=max(ans,__gcd(q[i-1],h[i+1]));
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1280
#include<stdio.h>
int main(){
  int sx[200],sy[200];
  int hx[1000],hy[1000];
  int n,m,i,j,k,x,y;
  while(1){
    scanf("%d",&n);
    if(!n)break;
    for(i=0;i<n;i++){
      scanf("%d %d",&sx[i],&sy[i]);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++){
      scanf("%d %d",&hx[i],&hy[i]);
    }
    for(i=0;i<m;i++){
      x=hx[i]-sx[0];
      y=hy[i]-sy[0];
      for(j=1;j<n;j++){
	for(k=0;k<m;k++){
	  if(sx[j]+x==hx[k]&&sy[j]+y==hy[k])break;
	}
	if(k==m)break;
      }
      if(j==n)break;
    }
    printf("%d %d\n",x,y);
  }
  return 0;
}

Measured memory_bytes: 608
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b){
if(a<b){return gcd(b,a);}
else if(a%b){return gcd(b,a%b);}
else{return b;}
}
ll prime(ll x) {
	ll i;
	if (x < 2)return 0;
	else if (x == 2) return 1;
	if (x % 2 == 0) return 0;
	for (i = 3; i*i <= x; i += 2) {
		if (x%i == 0) return 0;
	}
	return 1;
}
ll MOD = 1e9+7;
ll cnt[1010];
ll divide(ll m )
{
	while (m != 1) {
		for (ll i = 2; ; i++)
			if (m % i == 0){
				m /= i;
				cnt[i]++;
				break;
			}
	}
}
int main(){
  ll N;
  cin>>N;
  ll ans=1;
    for (ll i = 1; i <= N; i++){
		divide(i);
	}
  	for (ll i = 2; i <= N; i++){
		if (cnt[i]){
			ans *= (cnt[i] + 1);
			ans %= MOD;
		}
	}
 cout << ans << endl;
}

Measured memory_bytes: 256
n, q = gets.split.map(&:to_i)
used = Array.new(n,false)

g = Array.new(n){[]}
(n-1).times do
  a,b = gets.split.map{ |i| i.to_i - 1 }
  g[a].push(b)
  g[b].push(a)
end

points = Array.new(n,0)
q.times do |i|
  node,x = gets.split.map(&:to_i)
  node -= 1
  points[node] += x
end

que = [0]

while que.size != 0 do
  node = que.shift
  used[node] = true
  g[node].each do |k|
    next if used[k]
    points[k] += points[node]
    que.push(k) unless used[k]
  end
end

puts points.join(' ')

Measured memory_bytes: 27388
//19/01/2020
#include<bits/stdc++.h>

using namespace std;

#define debug printf("Debug\n");
#define ll long long
#define ull unsigned long long

#define pi acos(-1.0)
#define mod 1000000007

#define p_b(x) push_back(x)
#define m_p(x) make_pair(x,y)

#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define in_fre  freopen("in.txt", "r", stdin);
#define out_fre freopen("out.txt", "w", stdout);

struct Node{
    ll val,pos;
};
vector<ll>v[15];

ll cnt[15][15];

ll GetFirstDig(ll n){
    ll t=0;
    while(n>=1){
        t=n%10;
        n/=10;
    }
    return t;
}

ll saved[200005];

int main(){
    _fastio
    ll n;
    cin>>n;

    for(ll i=1;i<=n;i++){
        v[i%10].push_back(i);
    }
    ll ans=0;
    for(ll i=0;i<10;i++){
        for(ll j=0;j<v[i].size();j++){
            ll x=GetFirstDig(v[i][j]);
            saved[v[i][j]]=x;
            cnt[i][x]++;
        }
    }

    for(ll i=1;i<=n;i++){
        ll f=saved[i];
        ll l=i%10;
        ans+=cnt[f][l];
    }

    cout<<ans<<endl;



    return 0;
}


Measured memory_bytes: 3892
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {

	int N; cin >> N;

	
	int pow_ten = 1;
	int repsept = 7;
	int cnt = 1;
	while(cnt < pow(10,6) and repsept % N != 0) {
		pow_ten *= 10;
		pow_ten %= N;
		int next = pow_ten * 7;
		next %= N;
		repsept %= N;
		repsept += next;
		cnt++;
	}
	if (cnt == pow(10,6)) {
		cout << -1 << endl;	
	}else {
		cout << cnt << endl;
	}

	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K, y = 1;
  cin >> N >> K;
  
  
 
  // ここにプログラムを追記
  for (int i = 0; i < N; i++) {
    if (y + K >= y * 2) {
      y *= 2;
    }
    else {
      y += K;
    }
  }
  cout << y << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
    #include<ext/pb_ds/assoc_container.hpp> 
    #include<ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    using namespace std;
    template <typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    #define int long long  
    typedef long double ld;
    #define pb push_back
    #define f(i,a,b) for(int i=a;i<b;i++)
    #define fd(i,a,b) for(int i=a-1;i>=b;i--)
    #define pf push_front
    #define fi first
    #define se second
    #define INF 1e12
    const int mod=1e9+7;
    int cnt=0; 
    signed main() {

    ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
   /* #ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("INPUT.txt", "r", stdin);
    // for writing output to output.txt
    freopen("OUTPUT.txt", "w", stdout);
    #endif*/
    
    // -------------------------------------Code starts here--------------------------------------------------------------------- 
    int t=1;
     //cin>>t;
    while(t--)
    {
      int n;
      cin>>n;
      int a[n][3];
      f(i,0,n)
      {
        cin>>a[i][0]>>a[i][1]>>a[i][2];
      }
      int dp[n][3];
      f(i,0,n)
      f(j,0,3)
      dp[i][j]=0;
      dp[0][0]=a[0][0];
      dp[0][1]=a[0][1];
      dp[0][2]=a[0][2];
      f(i,1,n)
      {
        dp[i][0]+=max(dp[i-1][1],dp[i-1][2])+a[i][0];
        dp[i][1]+=max(dp[i-1][0],dp[i-1][2])+a[i][1];
        dp[i][2]+=max(dp[i-1][1],dp[i-1][0])+a[i][2];
      }
      cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
    } 

}

Measured memory_bytes: 4992