akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;}
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
       string N;
       cin >> N;
       ll sm = 0;
       rep(i, 0, len(N)) {
               sm += N[i] - '0';
       } 
       if (stoll(N) % sm == 0) {
               cout << "Yes" << endl;
       }  else {
               cout << "No" << endl;
       }
}

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

string S;

int main(int argc, char* argv[]){
  cin >> S;
  bool n,s,e,w;
  n=s=e=w=false;
  for(int i = 0; i < S.size(); i++){
	if(S[i]=='N') n++;
	if(S[i]=='S') s++;
	if(S[i]=='E') e++;
	if(S[i]=='W') w++;
  }
  if(((n&&s)||(!n&&!s))&&((e&&w)||(!e&&!w))) printf("Yes\n");
  else printf("No\n");
  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2 * (10 ** 6))
n, m = map(int, input().split())
edges = [[] for i in range(n)]
visit = [False for i in range(n)]
def dfs(v):
    visit[v] = True
    for i in edges[v]:
        if not visit[i]:
            dfs(i)
for i in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
cnt = 0
for i in range(n):
    if not visit[i]:
        dfs(i)
        cnt += 1
print(cnt - 1)

Measured memory_bytes: 48184
n = int(input())
a = [list(map(int, input().split())), list(map(int, input().split()))]
count = 0
answer = 0
i = 0
for k in range(n):
    i = 0
    for j in range(n):
        count += a[i][j]
        if j == k:
            i = 1
            count += a[i][j]
    answer = max(answer, count)
    count = 0

print(answer)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

struct Edge {
	int to, w;
};

typedef vector< vector<Edge> > Graph;

#define INF 1e9

bool f(Graph& G, int m, int M) {
	vector<bool> flag(G.size(), false);
	stack<int> S; S.push(0);
	int cnt = 0;
	while ( !S.empty() ) {
		int n = S.top(); S.pop();

		if (flag[n]) continue;
		flag[n] = true;
		++cnt;

		for (int i = 0; i < G[n].size(); ++i) {
			Edge& e = G[n][i];
			if (m <= e.w && e.w <= M) {
				S.push(e.to);
			}
		}
	}
	return cnt == G.size();
}

int main() {
	int N, M;
	while ( cin >> N >> M, N || M ) {
		Graph G(N);
		vector<int> v;
		for (int i = 0; i < M; ++i) {
			int a, b, w; cin >> a >> b >> w; --a, --b;
			G[a].push_back( (Edge){b, w} );
			G[b].push_back( (Edge){a, w} );
			v.push_back(w);
		}

		sort( v.begin(), v.end() );
		v.erase( unique(v.begin(), v.end()), v.end() );

		int ans = -1;
		for (int i = 0; i < v.size(); ++i) {
			int l = i-1, r = v.size()-1; // (l, r]
			while ( l < r-1 ) {
				int m = (l + r) / 2;
				if ( f(G, v[i], v[m]) ) {
					r = m;
				}
				else {
					l = m;
				}
			}

			int m = v[i], M = v[r];
			if ( (ans < 0 || M-m < ans) && f(G, m, M) ) ans = M-m;
		}
		cout << ans << endl;
	}
}

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

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

    int x,y;
    x = c/b;
    if(c%b>0)x++;
    y = a/d;
    if(a%d>0)y++;

    if(x<=y){
        cout<<"Yes";
    }else{
        cout<<"No";
    }

    return 0;
}

Measured memory_bytes: 3588
#include<string>
#include<stdio.h>

using namespace std;
int a[3];
int aa, b, c;

int main(void) {
	for (int i = 0; i < 3; i++){
		scanf("%d", &a[i]);
	}
	aa = a[2] / a[0];
	b = aa * a[1];

	printf("%d", b);
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define inf 1e+9
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define msg(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define pri(a) cout << a << endl;

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

  ll n,m,ans=0;
  cin >> n >> m;




  pri(n*(n-1)/2+m*(m-1)/2);

}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
typedef pair<int,int> P;
typedef pair<double,double> P_f;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define reprev(i, n) for (int i = (int)n - 1; i >= 0; i--)
#define MAX 100100
#define MAX_N 200100
#define MAX_T 2001001
#define SENTINEL 20010010010
#define NIL -1
static const int INF = 1 << 29;
const ll INFTY = 1LL<<50;
int n,a[101];
float sum;

int main(){
    cin>>n;rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    float mean=sum/(float)n;
    int less=(int)mean;
    int average;
    if(mean-less<less+1-mean)average=less;
    else average=less+1;
    int ans=0;
    rep(i,n){
        ans+=(average-a[i])*(average-a[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int MOD = 1000000007;
string S;

void add(long long &a, long long b){
    a += b;
    if (a >= MOD) a -= MOD;
}

long long dp[210000][5];

int main(){
    cin >> S;
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i=0;i<S.size(); ++i){
        for(int j=0;j<5;j++){
            if(S[i] != '?') add(dp[i+1][j], dp[i][j]);
            else add(dp[i+1][j], dp[i][j] * 3 % MOD);
        }
        if (S[i] == 'A' || S[i] == '?') add(dp[i+1][1], dp[i][0]);
        if (S[i] == 'B' || S[i] == '?') add(dp[i+1][2], dp[i][1]);
        if (S[i] == 'C' || S[i] == '?') add(dp[i+1][3], dp[i][2]);
    }
    cout << dp[S.size()][3] << endl;
}

Measured memory_bytes: 8704
import sys

for line in sys.stdin:
    n = int(line)
    count = 0
    for i in range(0, 10):
        for j in range(0, 10):
            for k in range(0, 10):
                for l in range(0, 10):
                    if i + j + k + l == n:
                        count += 1
    print(count)



Measured memory_bytes: 5596
#include<stdio.h>

int size, A[2000001];

void maxHeapify(int i){
  int l, r, largest, t;
  l = 2*i;
  r = 2*i+1;
  if ( l <= size && A[l] > A[i] ) largest = l;
  else largest = i;
  if ( r <= size && A[r] > A[largest] ) largest = r;
  if ( largest != i ){
    t = A[i]; A[i] = A[largest]; A[largest] = t;
    maxHeapify(largest);
  }
}

main(){
  scanf("%d", &size);
  int i;
  for ( i = 1; i <= size; i++ ) scanf("%d", &A[i]);
  
  for ( i = size/2; i >= 1; i-- ) maxHeapify(i);

  for ( i = 1; i <= size; i++ ) {
    printf(" %d", A[i]);
  }
  printf("\n");
  

  
  return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<int, pair<int, int>> PP;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const int mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    cin >> n;
    vector<int> cnt(4, 0);
    for(int i = 0; i < n; ++i){
        char c;
        cin >> c;
        if(c == 'P')    ++cnt[0];
        if(c == 'W')    ++cnt[1];
        if(c == 'G')    ++cnt[2];
        if(c == 'Y')    ++cnt[3];
    }

    if(cnt[3] == 0){
        cout << "Three\n";
    }
    else{
        cout << "Four\n";
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;
using ld = long double;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if(s[i] == '1'){
            s[i] = '9';
        } else{
            s[i] = '1';
        }
    }

    cout << s << endl;
    return 0;
}

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

int main() {
  int N; // N計算の数
  cin >> N;
     
  // ここにプログラムを追記
  for (int i = 0; i < N; i++) {
    string c;
    cin >> c;
    
    if (c == "Y"){
      cout << "Four";
      break;
    }
    
    if (i+1 == N){
      cout << "Three";
    }
  } 
}

Measured memory_bytes: 256
#include <stdio.h>

int zero[4] = {1, 2, 4, 3};
int one[4] = {0, 3, 5, 2};
int two[4] = {0, 1, 5, 4};

// getNeighbors gets the correct array of zero, one, and two given a number 0, 1, 2, 3, 4, or 5.
int *getNeighbors(int index)
{
  if (index > 2)
     index = 5 - index;
  switch (index)
    {
    case 0:
      return zero;
    case 1:
      return one;
    case 2:
      return two;
    }
}

// chooseIndex chooses to search zero, one, or two for the purposes of getIndex2(int,int).
int chooseIndex(int index0, int index1)
{
  int i;
  int indices[3] = {};
  indices[index0 < 3 ? index0 : 5 - index0] = 1;
  indices[index1 < 3 ? index1 : 5 - index1] = 1;
  for (i = 0; i < 3; i++)
    if (!indices[i])
      return i;
}

// getIndex2 determines the 3rd index in the counter-clockwise rotation of index0 -> index1 -> index2.
int getIndex2(int index0, int index1)
{
  int *toSearch, i;
  int index = chooseIndex(index0, index1);
  toSearch = getNeighbors(index);
  for (i = 0; i < 4; i++)
    {
      if (toSearch[i] == index0)
	if (toSearch[(i + 1) % 4] == index1)
	  return index;
	else
	  return 5 - index;
    }
}

int main(void)
{
  int die0[6], die1[6], i, index0, index1;
  for (i = 0; i < 6; i++)
    scanf(" %d", die0 + i);
  for (i = 0; i < 6; i++)
    scanf(" %d", die1 + i);
  // set index0
  for (index0 = 0; index0 < 6; index0++)
    {
      if (die0[0] != die1[index0])
	continue;
      //printf("index0: %d\n", index0); // EXTRA
      // set index1
      int *neighbors = getNeighbors(index0);
      for (i = 0; i < 4; i++)
	{
	  index1 = neighbors[i];
	  if (die0[1] != die1[index1])
	    continue;
	  //printf("index1: %d\n", index1); // EXTRA
	  // find the 3rd counter-clockwise index of die1
	  int index2 = getIndex2(index0, index1);
	  //if (index0 == 3 && index1 == 5) // EXTRA
	  //printf("index2: %d\n", index2); // EXTRA
	  if (die0[2] != die1[index2])
	    continue;
	  // check the last three faces are equivalent
	  if (die0[3] != die1[5 - index2])
	    continue;
	  if (die0[4] != die1[5 - index1])
	    continue;
	  if (die0[5] != die1[5 - index0])
	    continue;
	  printf("Yes\n");
	  return 0;
	}
    }
  printf("No\n");
  return 0;
}



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

int main()
{
  int64_t N, K, C;
  cin >> N >> K >> C;
  vector<bool> vb(N);
  vector<int> vl(N, -1), vr(N, -1);
  char c;
  for (int i = 0; i < N; i++)
  {
    cin >> c;
    vb[i] = (c == 'o');
  }
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    if (cnt >= K)
    {
      break;
    }
    if (!vb[i])
      continue;
    vl[i] = ++cnt;
    i += C;
  }
  int k = 0;
  for (int i = N - 1; i >= 0; i--)
  {
    if (k >= K)
    {
      break;
    }
    if (!vb[i])
      continue;
    k++;
    vr[i] = (cnt + 1) - k;
    i -= C;
  }
  queue<int> ans;
  for (int i = 0; i < N; i++)
  {
    if (vl[i] > 0 && vl[i] == vr[i])
    {
      ans.push(i + 1);
    }
  }
  while (ans.size())
  {
    cout << ans.front() << endl;
    ans.pop();
  }
}

Measured memory_bytes: 5624
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
priority_queue<ll,vector<ll> ,greater<ll> >q;
int n,k;
struct node{
    ll s,t;
}e[maxn];
bool cmp(node a,node b){
    return a.t>b.t;
}
int vis[maxn];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&e[i].s,&e[i].t);
    sort(e+1,e+n+1,cmp);
    ll gs=0;
    ll cnt=0;
    for(int i=1;i<=k;i++){
        if(!vis[e[i].s])gs++,vis[e[i].s]=1;
        else q.push(e[i].t);
        cnt+=e[i].t;
    }
    ll ans=cnt+gs*gs;
    for(int i=k+1;i<=n;i++){
        if(!vis[e[i].s]&&!q.empty()){
            ll t=q.top();q.pop();
            gs++;cnt-=t;cnt+=e[i].t;
            vis[e[i].s]=1;
            ans=max(ans,cnt+gs*gs);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2812
#include<cstdio>
#include<algorithm>
int N,a[100010];
bool Q[100010];
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",a+i);
	std::sort(a,a+N);
	bool*h=Q,*t=Q,*ed=Q+N;
	for(int i=0;i<N;i++){
		int la=i?a[i-1]:0;
		if(h<t)h++,t<ed?*t=!t[-1]||(a[i]-la&1),t++:0;
		for(int j=la+1;j<=a[i]&&t<ed;j++)*t++=(a[i]-j)%2;
	}
	puts(*h?"First":"Second");
}

Measured memory_bytes: 640
n,m = map(int,input().split())
h = list(map(int,input().split()))
a = [0 for i in range(m)]
b = [0 for i in range(m)]
for i in range(m):
	a[i],b[i] = map(int,input().split())
#良い展望台 -> 標高の一番高い
v = [[] for i in range(n)]
for i in range(m):
	v[a[i]-1].append(b[i]-1)
	v[b[i]-1].append(a[i]-1)
count = 0
for i in range(n):
	max = h[i]
	cnt = h[i]
	unta = 1
	for j in v[i]:
		cnt = h[j]
		if max <= cnt:
			max = cnt
			unta = 0
	count += unta
print(count)

Measured memory_bytes: 37392
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
string s[3];
int v[3], p;

void fim() {
    
}

int main(int argc, char ** argv) {
    rep(i, 0, 3) cin >> s[i];
    while(1 < 2) {
        if(v[p] == s[p].size()) {
            printf("%c\n", p+'A');
            return 0;
        }
        int P = s[p][v[p]]-'a';
        v[p]++;
        p = P;
    }
    return 0;
}


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

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];
  int res = A[0];
  for (int i = 1; i < N; i++)
    res = gcd(res, A[i]);
  cout << res << '\n';
  return 0;
}


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

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

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

#define rep(i,a,n) for(int (i)=a;(i)<(int)(n);(i)++)
#define rrep(i,a,n) for(int (i)=(n)-1;(i)>=a;(i)--)
#define all(x) (x).begin(),(x).end()

typedef long long ll;

const int INF = 1e9;

int main() {
	while (true) {
			int h,w;
			cin >> h >> w;
			if (h == 0 and w == 0) {
					return 0;
			}
			rep(i,0,h) {
					rep(j,0,w) cout << ((i + j) % 2 ? "." : "#");
					cout << endl;
			}
			cout << endl;
	}	
}

Measured memory_bytes: 3016
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
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)*}
    };
}
 
#[allow(unused_macros)]
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)*}
    };
}
 
#[allow(unused_macros)]
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")
    };
}

// -----------------------------------------------------------------------------
// main
// -----------------------------------------------------------------------------
fn main(){
    input!{
        n: u64,
        a: [u64; n]
    }
    println!("{}", a.iter().sum::<u64>() - n);
}



Measured memory_bytes: 4352
N, K = map(int, input().split())
A = list(map(int, input().split()))

mod = 10 ** 9 + 7
ans = 0

if K == 1:
    for i in range(N-1):
        for j in range(i+1, N):
            if A[i] > A[j]:
                ans += 1
        ans %= mod
    print(ans)
    exit()


for i in range(N):
    tmp = 0
    for j in range(i+1, N):
        if A[i] > A[j]:
            tmp += ((K * (K+1) // 2) % mod)
    for j in range(i):
        if A[i] > A[j]:
            tmp += ((K * (K-1) // 2) % mod)
    tmp %= mod
    ans += tmp

print(ans % mod)


Measured memory_bytes: 3188
n = int(input())
set_abc = {"a", "b", "c"}
abc_array = [{key: int(value) for key, value in zip(set_abc, input().split())} for y in range(n)]

# a or b or cを選んだときの報酬の最高値
dp = [{key: 0 for key in set_abc} for x in range(n)]
res = 0
for index in range(n):
    if index == 0:
        dp[index] = abc_array[index]
        continue
    for key, value in abc_array[index].items():
        candidate_key = set_abc - set(key)
        dp[index][key] = max(dp[index - 1][candidate_key.pop()] + value, dp[index - 1][candidate_key.pop()] + value)

print(max(dp[-1].values()))


Measured memory_bytes: 83156
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

int H,W;
char S[51][51];

int ans = 0;

void solve(){
	//BFS
	//pair<h,w>
	queue<pair<int,int>> q;
	q.push(pair<int,int>(1,1));
	//h,wをすでに訪れているなら
	vector<vector<int>> used(H+1,vector<int>(W+1,0));
	used[1][1] = 1;
	for(int h=1;h<=H;h++){
    	for(int w=1;w<=W;w++){
    		//S[h][w]が黒いマスならused[h][w]=-1にしておく
    		if(S[h][w]=='#') used[h][w]=-1;
    		//あらかじめ白いマスの数をカウントしておく
    		if(S[h][w]=='.') ans++;
    	}
    }
	while(!q.empty()){
		int y = q.front().first;
		int x = q.front().second;
		if(y==H && x==W) break;
		q.pop();
		if(y+1<=H){
			if(used[y+1][x]==0){
				q.push(pair<int,int>(y+1,x));
				used[y+1][x] = used[y][x] + 1;
			}
		}
		if(x+1<=W){
			if(used[y][x+1]==0){
				q.push(pair<int,int>(y,x+1));
				used[y][x+1] = used[y][x] + 1;
			}
		}
		if(y-1>=1){
			if(used[y-1][x]==0){
				q.push(pair<int,int>(y-1,x));
				used[y-1][x] = used[y][x] + 1;
			}
		}
		if(x-1>=1){
			if(used[y][x-1]==0){
				q.push(pair<int,int>(y,x-1));
				used[y][x-1] = used[y][x] + 1;
			}
		}
	}
    ans = ans - used[H][W];
    if(ans<0 || used[H][W]==0) ans = -1;
}
 
int main(){
    cin >> H >> W;
    for(int h=1;h<=H;h++){
    	for(int w=1;w<=W;w++){
    		cin >> S[h][w];
    	}
    }
 
    solve();

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

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<deque>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<vector<int>> vvi;

#define rep(i, a, n)  for(int i=a; i<n; i++)
#define REP(i, n)  for(int i=0; i<(int)(n); i++)
#define REPS(i, n)  for(int i=1; i<=(int)(n); i++)
#define PER(i, n) for(int i=(int)(n)-1; i>= 0; i--)
#define PERS(i, n)  for(int i=(int)(n); i>0; i--)
#define FOR(i, c) for(__typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
#define RFOR(i, c)  for(__typeof((c).rbegin()) i=(c).rbegin(); i!=(c).end(); i++)
#define ALL(container)  (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) (container).size()
#define FILL0(n)  setfill('0') << right << setw(n)
#define mp(a, b)  make_pair(a, b)
#define toLower(c)  c+0x20
#define toUpper(c)  c-0x20
#define pb  push_back
#define eb  emplace_back

const int INF = 1e9;
const long long LLINF = 1e18;
const ull MOD = 998244353;
const int MSIZE = 100007;
const double Pi = 3.14159265358979323146;

int main(){
  int match[10] = {6,2,5,5,4,5,6,3,7,6};
  int n, m; cin >> n >> m;
  vector<int> num(m), dp(n+100, -INF);
  REP(i, m){
    cin >> num[i];
  }
  dp[0]=0;
  sort(RALL(num));
  string ans = "";
  for(int i=1; i<=n; i++){
    REP(j, m){
      if(i-match[num[j]]<0) continue;
      dp[i] = max(dp[i], dp[i-match[num[j]]]+1);
    }
  }
  //cout << n << ":" << ans << endl;

  while(n>0){
    REP(j, m){
      if(n-match[num[j]]<0) continue;
      if(dp[n-match[num[j]]]==dp[n]-1){
        ans += ('0'+num[j]);
        n-=match[num[j]];
        //cout << n << ":" << ans << endl;
        break;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
abcd = input()
for i in range(1 << 4):
    exp = ''
    for j in range(3):
        op = '+' if i & (1 << j) else '-'
        exp += abcd[j] + op
    exp += abcd[3]
    if eval(exp) == 7:
        print(exp + '=7')
        break


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(){
    int n,r;
    while(cin>>n>>r,n,r){
        int data[50],tmp[50];
        for(int i=0;i<n;i++){
            data[i]=n-i;
            tmp[i]=n-i;
        }
        for(int i=0;i<r;i++){
            int p,c;
            cin>>p>>c;
            for(int j=0;j<p+c-1;j++){
                if(j<p-1){
                    tmp[j+c]=data[j];
                }else{
                    tmp[j-p+1]=data[j];
                }
            }
            for(int j=0;j<n;j++){
                data[j]=tmp[j];
            }
        }
        cout<<data[0]<<endl;
    }
}

Measured memory_bytes: 3056
N,K = list(map(int,input().split()))
ans = 0

for i in range(N):
    b=i+1
    p=int(N/b)
    
    ans+=max(0,b-K)*p+max(0,N-p*b-K+1)
    if K==0:
        ans-=1

print(ans)

Measured memory_bytes: 3060
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)

INF = 1<<100
def BFS(n, E, i0=0):
    Q = deque([a for a in E[i0]])
    D = [INF] * n
    for a in E[i0]:
        D[a] = 1
    while Q:
        x = Q.popleft()
        for c in X[x]:
            if D[c] == INF:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [BFS(N, X, i)[i] for i in range(N)]
# print("Y =", Y)
mi = min(Y)
if mi == INF:
    print(-1)
else:
    for i in range(N):
        if Y[i] == mi:
            s = i
            break
    Z = [-1] * N
    for i in range(N):
        for j in X[i]:
            if Y[j] == mi:
                Z[i] = j
                break
    for i in range(N):
        s = Z[s]
    print(mi)
    for i in range(mi):
        s = Z[s]
        print(s+1)


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

AB = sorted(AB)
total=0
for i in range(N):
    if AB[i][1]>M:
        total = total + AB[i][0]*M
        break
    else:
        total = total + AB[i][0]*AB[i][1]
        M = M - AB[i][1]

print(total)

Measured memory_bytes: 90244
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
	private static void solve(FastScanner fr) {
		int n = fr.nextInt();
		// long[] a = new long[n];
		long a = 0;
		long psum= 0;;
		long res = 0;
		long div = ((long)1e9)+7;
		for(int i=0; i<n; i++) {
			a = fr.nextLong();
			if(i>0)
				res += (a*psum)%div;
			psum = (psum+a)%div;
		}
		sout(res%div);
	}
    public static void main(String[] args) {
		FastScanner fs = new FastScanner();
		int n = 1;
		// int n = fs.nextInt();
		while (n-- > 0)	{
			solve(fs);
        }
    }

    private static void sout()          { System.out.println();  }
    private static void sout(String s)  { System.out.println(s); }
    private static void sout(int s)     { System.out.println(s); }
    private static void sout(long s)    { System.out.println(s); }
    private static void sout(double s)  { System.out.println(s); }
    
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try { st=new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); }
			return st.nextToken();
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		int nextInt() {	return Integer.parseInt(next()); }
		long nextLong() { return Long.parseLong(next()); }
		double nextDouble() { return Double.parseDouble(next()); }
	}
}


Measured memory_bytes: 52376
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
 
int main(){
    double L;
    cin >> L;
    
    cout << fixed << setprecision(10);
    cout << (L*L*L)/27 << endl;

}

Measured memory_bytes: 3784
#include<bits/stdc++.h>
#define INF 999999999

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    ll r = a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int main(){
    ll n;
    cin >> n;
    ll a[100005];
    for(ll i = 0; i < n; i++)cin >> a[i];
    ll lg[100005];
    ll rg[100005];
    ll g = a[0];
    for(ll i = 0; i < n; i++)lg[i] = gcd(g, a[i]), g = lg[i];
    g = a[n-1];
    for(ll i = n-1; i>=0; i--)rg[i] = gcd(g, a[i]), g = rg[i];
    ll m = max(lg[n-2], rg[1]);
    for(ll i = 0; i < n-2; i++)m = max(gcd(lg[i], rg[i+2]), m);
    cout << m << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define NODE 100001
#define INF 1000000000000000000LL
//v[i][j]; j番目の辺。iからfirstへの有向辺で、コストはsecond。
vector<vector<pair<ll,ll> > > v(NODE);
ll dist[NODE];
int dijkstra(int start){
	//初期化
	for(int i = 0;i < NODE;i++)dist[i] = INF;
	dist[start] = 0;
	//priority_queueの宣言
	//pqに入れているのは(startからtoへの最短距離, to)
	//priority_queueの都合上、vのpairの順番とは逆にしている。
	priority_queue<P,vector<P>,greater<P> > pq;
	pq.push(make_pair(0,start));
	while(!pq.empty()){
		//現在見る者の中で、最もdistが小さいものを取り出す
		P now = pq.top();pq.pop();
		ll d = now.first;
		ll node = now.second;
		//すでに更新されていたりして、現在のが最適でなかったらスルー
		if(dist[node] < d)continue;
		//その点と辺を持つものに対して
		for(int i = 0;i < v[node].size();i++){
			ll opp_n = v[node][i].first;
			ll opp_d = v[node][i].second;
			//もし、distが更新できるならば、更新してpriority_queueに突っ込む
			if(dist[opp_n] > d + opp_d){
				dist[opp_n] = d + opp_d;
				pq.push(make_pair(dist[opp_n],opp_n));
			}
		}
	}
}

vector<vector<pair<ll,ll> > > v2(NODE);
ll dist2[NODE];
int dijkstra2(int start){
	//初期化
	for(int i = 0;i < NODE;i++)dist2[i] = INF;
	dist2[start] = 0;
	//priority_queueの宣言
	//pqに入れているのは(startからtoへの最短距離, to)
	//priority_queueの都合上、vのpairの順番とは逆にしている。
	priority_queue<P,vector<P>,greater<P> > pq;
	pq.push(make_pair(0,start));
	while(!pq.empty()){
		//現在見る者の中で、最もdistが小さいものを取り出す
		P now = pq.top();pq.pop();
		ll d = now.first;
		ll node = now.second;
		//すでに更新されていたりして、現在のが最適でなかったらスルー
		if(dist2[node] < d)continue;
		//その点と辺を持つものに対して
		for(int i = 0;i < v2[node].size();i++){
			ll opp_n = v2[node][i].first;
			ll opp_d = v2[node][i].second;
			//もし、distが更新できるならば、更新してpriority_queueに突っ込む
			if(dist2[opp_n] > d + opp_d){
				dist2[opp_n] = d + opp_d;
				pq.push(make_pair(dist2[opp_n],opp_n));
			}
		}
	}
}

int main(){
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	s--; t--;
	for(int i = 0; i < m; i++) {
		int ui, vi, ai, bi;
		cin >> ui >> vi >> ai >> bi;
		ui--; vi--;
		v[ui].push_back(make_pair(vi, ai));
		v[vi].push_back(make_pair(ui, ai));
		v2[ui].push_back(make_pair(vi, bi));
		v2[vi].push_back(make_pair(ui, bi));
	}
	dijkstra(s);
	dijkstra2(t);

	vector<pair<ll, ll>> cost;
	for(int i = 0; i < n; i++)
		cost.push_back(make_pair(dist[i] + dist2[i], i));
	sort(cost.begin(), cost.end());

	int j = 0;
	for(int i = 0; i < n; i++) {
		while(cost[j].second < i) j++;
		cout << (1000000000000000LL - cost[j].first) << endl;
	}

	return 0;
}


Measured memory_bytes: 19964
while True:
    n = int(input())
    if n==0:
        break
    for i in range(n):
        m,e,j = [ int(s) for s in input().split() ]
        if m == 100 or e == 100 or j == 100:
            print('A')
        elif (m+e)/2 >= 90:
            print('A')
        elif (m+e+j)/3 >= 80:
            print('A')
        elif (m+e+j)/3 >= 70:
            print('B')
        elif (m+e+j)/3 >= 50 and (m >= 80 or e>= 80):
            print('B')
        else:
            print('C')


Measured memory_bytes: 5620
n = gets.to_i
dp = Array.new(10**6 + 100, 10**8)
dp[0] = 0


(0..100000).each do |i|
  pow6 = 1
  pow9 = 1
  while pow6 + i <= n do
    dp[i + pow6] = [dp[i]+1, dp[i+pow6]].min
    pow6 *= 6
  end
  while pow9 + i <= n do
    dp[i + pow9] = [dp[i]+1, dp[i+pow9]].min
    pow9 *= 9
  end
end

puts dp[n]
  

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

struct UnionFind {
  vector<int> par;
  
  UnionFind(int N) {
    par = vector<int>(N, -1);
  }
  
  int root(int x) {
    if (par.at(x) < 0) return x;
    return par.at(x) = root(par.at(x));
  }
  
  bool unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) return false;
    if (par.at(rx) > par.at(ry)) swap(rx, ry);
    par.at(rx) += par.at(ry);
    par.at(ry) = rx;
    return true;
  }
  
  int size(int x) {
    return -par.at(root(x));
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  UnionFind tree(N);
  for (int i = 0; i < M; i++) {
    int A, B;
    cin >> A >> B;
    tree.unite(A - 1, B - 1);
  }
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans = max(ans, tree.size(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 4052
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,i = 0,j = 1,k = 0,ans = 0,z;scanf("%lld",&n);
  long long a[n],b[n],c[n],sita[n+1] = {};
  for(i=0;i<n;i++) scanf("%lld",&a[i]);
  for(i=0;i<n;i++) scanf("%lld",&b[i]);
  for(i=0;i<n;i++) scanf("%lld",&c[i]);
  sort(a,a+n);sort(b,b+n);sort(c,c+n);
  while(j <= n && k < n){
    if(b[j-1] < c[k]){
      sita[j] = ((j==0) ? n-k:sita[j-1]+n-k);j++;
    } else k++;
  }
  for(j;j<=n;j++) sita[j] = sita[j-1];
  for(i=0;i<n;i++){
    z = upper_bound(b,b+n,a[i])-b;
    ans += sita[n]-sita[z];
  }
  printf("%lld\n",ans);
}
  
  
    
  

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

using namespace std;

int main(){
  int n, k; cin >> n >> k;
  vector<int> a(n), dp(n, 1e9 + 10);
  for(int i = 0; i < n; i++) cin >> a[i];
  dp[n - 1] = 0;
  for(int i = n - 2; i >= 0; i--){
    for(int j = 1; j <= k; j++){
      if(i + j < n){
        dp[i] = min(dp[i], abs(a[i] - a[i + j]) + dp[i + j]);
      }
    }
  }
  cout << dp[0] << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
long long int N, a[114514], m, c, i;
 
int main(){
    scanf("%lld", &N);
    for(; i < N; ++i){
        scanf("%lld", a + i);
        m = max(m, a[i]);
    }
    for(i = 0; i < N; ++i){
        if(a[i] < m)++c;
        if(a[i] < m - 1)return puts("No") & 0;
    }
    if(c == 0 && *a == N - 1)return puts("Yes") & 0;
    puts(((c > m - 1) || (c < m * 2 - N)) ? "No" : "Yes");
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>
#include <bitset>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
using P = 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;}

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  double A, B, C, D, E, F; cin >> A >> B >> C >> D >> E >> F;

  double max_concentration = -1;
  double mass_all = 0, mass_sugar = 0;
  for (int i = 0; i < 35; ++i){
    for (int j = 0; j < 35; ++j){
      for (int k = 0; k < 3100; ++k){
        if (100 * A * i + 100 * B * j + C * k > F) continue;
        for (int m = 0; m < 3100; ++m){
          if (100 * A * i + 100 * B * j + C * k + D * m <= F && C * k + D * m <= E * (A * i + B * j)) {
            double a = 100 * A * i + 100 * B * j, b = C * k + D * m;
            double concentration = (100 * b) / (a + b);
            if (chmax(max_concentration, concentration)){
              mass_all = a + b;
              mass_sugar = b;
            }
          }
        }
      }
    }
  }
  cout << mass_all << " " << mass_sugar << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {

	int n;
	int a, b, c, d;
	cin >> n;
	cin >> a;
	cin >> b;
	cin >> c;
	cin >> d;
	string s;
	cin >> s;
	int i;
	for (i = a - 1; i <= c - 1; i++) {
		if ((s[i] == '#') && (s[i + 1] == '#')) {
			cout << "No";
			return 0;
		}
	}
	for (i = b - 1; i <= d - 1; i++) {
		if ((s[i] == '#') && (s[i + 1] == '#')) {
			cout << "No";
			return 0;
		}
	}
	if (c < d) {
		cout << "Yes";
		return 0;
	}
	else {
		for (i = b - 1; i <= d - 1; i++) {
			if ((s[i - 1] == '.') && (s[i + 1] == '.') && (s[i] == '.')) {
				cout << "Yes";
				return 0;
			}
		}
		cout << "No";
		return 0;
	}
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int L = scanner.nextInt();
    int N = scanner.nextInt();
    int[] x = new int[N];
    int[] y = new int[N];
    for (int i = 0; i < N; i++) {
      x[i] = scanner.nextInt();
      y[N - i - 1] = L - x[i];
    }
    long[] x2 = new long[N + 1];
    long[] y2 = new long[N + 1];
    for (int i = 1; i <= N; i++) x2[i] = x2[i - 1] + x[i - 1] * 2L;
    for (int i = 1; i <= N; i++) y2[i] = y2[i - 1] + y[i - 1] * 2L;

    long max = x[N - 1];
    for (int n = N - 1; n > 0; n--) {
      int m = N - n;
      max = Math.max(max, Math.max(
          x2[n - 1] - x2[Math.max(n - m - 1, 0)] + y2[m] - y2[Math.max(m - n, 0)] + x[n - 1],
          x2[n] - x2[Math.max(n - m, 0)] + y2[m - 1] - y2[Math.max(m - n - 1, 0)] + y[m - 1]
      ));
    }
    max = Math.max(max, y[N - 1]);
    System.out.println(max);
  }
}


Measured memory_bytes: 93856
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <functional>
#include <algorithm>

int main() {
  std::string s;
  unsigned K;
  std::cin >> s >> K;
  std::vector<std::string> cand;
  for (unsigned i = 0; i < s.size(); ++i) {
    std::string buf;
    for (unsigned j = 0; j < K && i + j < s.size(); ++j) {
      buf += s[i + j];
      cand.push_back(buf);
    }
  }
  std::sort(cand.begin(), cand.end());
  cand.erase(std::unique(cand.begin(), cand.end()), cand.end());
  std::cout << cand[K - 1] << std::endl;
  return 0;
}

Measured memory_bytes: 1160
using System;

namespace TestConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = int.Parse(Console.ReadLine());
            var i = 1;

            do
            {
                var x = i;

                if (x % 3 == 0)
                {
                    Console.Write($" {i}");
                }
                else
                {
                    do
                    {
                        if (x % 10 == 3)
                        {
                            Console.Write($" {i}");
                            break;
                        }
                        x = x / 10;
                    } while (x != 0);
                }
            } while (++i <= input);

            Console.WriteLine();
        }
    }
}



Measured memory_bytes: 17904
#include<bits/stdc++.h>
#define eps 1e-6
#define ll long long
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#define int long long
#define MEM(x,y) memset(x,y,sizeof(x))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define fi first
#define se second
#define endl "\n"
#define pii pair<int,int>
#define fi first
#define se second
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll Max(ll a,ll b){return a>=b?a:b;}
ll Min(ll a,ll b){return a<=b?a:b;}
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res,t;res=1;t=a%c;while(b){if(b&1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
using namespace std;
//head file
int main()
{
    char c;
    cin>>c;
    if(islower(c))
        cout<<"a";
    else
        cout<<"A";
    return 0;
}


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

int main () {
  string s;
  cin >> s;
  int a = 0;
  int b = s.size();
  for (int i = 0; i < s.size(); i++) {
    a++;
    if (s.at(i) == 'A') {
      break;
    }
  }
  for (int i = s.size(); i > 0; i--) {
    b--;
    if (s.at(i-1) == 'Z') {
      break;
    }
  }
  cout << b-a+2 << endl;
}


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

const ll INF = 1LL << 60;
const int mod = 1e9 + 7;

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll>> res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

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

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

ll N;
vector<ll> A;
int main() {
    cin >> N;
    A.resize(N);
    rep(i, N) cin >> A[i];

    // 最小公倍数を求める
    map<ll, ll> mp;
    rep(i, N) {
        vector<pair<ll, ll>> v = prime_factorize(A[i]);
        rep(j, v.size()) {
            mp[v[j].first] = max(mp[v[j].first], v[j].second);
        }
    }

    // for (auto m : mp) {
    //     cout << m.first << " " << m.second << endl;
    // }
    mint lcm = 1;
    for (auto m : mp) {
        for (int c = 0; c < m.second; c++) {
            lcm *= m.first;
        }
    }
    // cout << lcm << endl;

    mint ans = 0;
    for (int i = 0; i < N; i++) {
        mint tmp = A[i];
        ans += lcm / tmp;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4192
#include <stdio.h>
 
typedef long long ll;
 
ll lcm(ll a, ll b);
ll gcd(ll a, ll b);
 
ll lcm(ll a, ll b){
    return a/gcd(a,b)*b;
}
 
ll gcd(ll a, ll b){
    if(a<b) return gcd(b,a);
    if(b==0)return a;
    return gcd(b,a%b);
}
 
 
int main(){
    int n,i;
    ll ans,t;
 
    scanf("%d",&n);
 
    ans=1;
    for(i=0;i<n;i++){
        scanf("%lld",&t);
        ans=lcm(ans,t);
    }
 
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
struct BIT {
    int N;
    vector<T> dat;

    // [0, N], 1-indexing!!!
    explicit BIT(int n): N(n), dat(N + 1, 0) {}

    T sum(int i) {
        T s = 0;
        while(i > 0) {
            s += dat[i];
            i -= i & -i;  // i = i & (i-1)
        }

        return s;
    }

    void add(int i, T x) {
        while(i <= N) {
            dat[i] += x;
            i += i & -i;
        }
    }

    // min_x {x | v1 + v2 + ⋯ + vx ≧ w}
    // Assuming v_q >= 0
    int lower_bound(T w) {
        if (w <= 0) return 0;

        int x = 0; T k = 1;
        while (k * 2 <= N) k <<= 1;
        for (; k > 0; k /= 2) {
            if (x + k <= N && dat[x + k] < w) {
                w -= dat[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, Q;
    cin >> N >> Q;

    vll c(N);
    REP(i, N) cin >> c[i];

    vector<pair<pair<int, int>, int>> query;
    REP(i, Q) {
        int l, r; cin >> l >> r;
        query.pb({{r, l}, i});
    }

    sort(ALL(query));

    vector<ll> last(N, -1);

    BIT<ll> bit(N);

    int r_prev = 1;
    vector<pair<int, ll>> ans;
    REP(i, Q) {
        auto p = query[i];
        int l = p.fi.se, r = p.fi.fi;

        for(int j = r_prev; j <= r; ++j) {
            if (last[c[j - 1]] > 0) bit.add(last[c[j - 1]], -1);
            last[c[j - 1]] = j;
            bit.add(j, 1);
        }
        r_prev = r;

        ans.eb(p.se, bit.sum(r) - bit.sum(l-1));
    }

    sort(ALL(ans));

    REP(i, ans.size()) {
        print(ans[i].se);
    }
    
}


Measured memory_bytes: 33284
#include <iostream>

using namespace std;

int main(){
        int n,m;
        cin >> n >> m; 
        while(n){
                bool *a = new bool[n];
                for(int i = 0; i<n; i++) a[i] = true;
                int idx = n-1;
                int _n = n; 
                while(n--){
                        int c = m; 
                        while(c){
                                idx = (idx+1)%_n;
                                if(a[idx]) --c;
                        }  
                        a[idx] = false;
                }  
                delete a; 
                cout << ++idx << endl;
                cin >> n >> m; 
        }  
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >>d;
  
  if (a + b > c + d )
    cout << "Left" << endl;
  else if (a + b == c + d )
    cout << "Balanced" << endl;
  else
    cout << "Right" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<utility>
#include<queue>
using namespace std;

int main(){
    int n,q,time,cnt_time=0;
    string name;
    queue<pair<string,int> >que;
    cin>>n>>q;
    for(int i=0; i<n; i++){
        cin>>name>>time;
        que.push(make_pair(name,time));
    }
    while(!que.empty()){
        pair<string,int> top = que.front();
        que.pop();
        if(top.second<=q){
            cnt_time += top.second;
            cout<< top.first << " "<< cnt_time <<endl;
        }else{
            cnt_time += q;
            que.push(make_pair(top.first, top.second-q));
        }
    }
}


Measured memory_bytes: 6312
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF (INT_MAX / 4)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
/* clang-format off */
#define TIMER_S(start) chrono::system_clock::time_point start = chrono::system_clock::now();
#define TIMER_E(end) chrono::system_clock::time_point end = chrono::system_clock::now();
#define TIME(start, end) cout << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count()) << "ms" << "\n";
/* clang-format on */

int main() {
  int n,ans=0;
  cin >> n;
  unordered_map<string, int> m;
  REP(i, n) { string s;
    cin >> s;
    if (m.count(s))
      m.at(s)++;
    else
      m[s] = 1;
    }
    for(auto x : m){
      ans++;
    }
    cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 17692
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;

const int MX = 1500000;
bool sieve[MX];

int main() {
    memset(sieve, false, sizeof sieve);
    sieve[0] = sieve[1] = true;
    for (int i=2; i*i<MX; ++i) {
        if ( ! sieve[i]) {
            for (int j=i*i; j<MX; j+=i) {
                sieve[j] = true;
            }
        }
    }
    int n;
    while (cin >> n, n) {
        int l, h;
        for (int i=n; ; ++i) {
            if ( ! sieve[i]) {
                h = i; break;
            }
        }
        for (int i=n; ; --i) {
            if ( ! sieve[i]) {
                l = i; break;
            }
        }
        cout << h-l << endl;
    }
    return 0;
}

Measured memory_bytes: 2632