akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

class Main {
    static Scanner scanner = new Scanner();

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        char[] s = scanner.next().toCharArray();
        long ans = 0;
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == s[i]) {
                ans++;
            }
        }
        ans += k * 2;
        System.out.println(Math.min(ans, n - 1));
    }

    static class Scanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

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

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

Measured memory_bytes: 25044
#include <bits/stdc++.h>
using namespace std;
int main() {
    int m,n,i,cnt=0,mn=INT_MAX;
    cin>>n;
    int a[n];
    for(i=0 ; i<n;i++){
        cin>>a[i];
    }
    for(i=0 ; i<n;i++){
        mn=min(a[i],mn);
        if(mn==a[i])
        cnt++;
    }
    cout<<cnt;
}

Measured memory_bytes: 1024
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  char c; cin >> c;
  if (c == 'A') cout << 'T' << '\n';
  if (c == 'T') cout << 'A' << '\n';
  if (c == 'C') cout << 'G' << '\n';
  if (c == 'G') cout << 'C' << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3592
//package atcoder;
 
import java.util.*;
import java.math.BigDecimal;
 
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String s = null;
		if(a<b) {
			s = String.valueOf(a);
			for(int i=1;i<b;i++) {
				s += String.valueOf(a);
			}
		}
		else {
			s = String.valueOf(b);
			for(int j=1;j<a;j++) {
				s += String.valueOf(b);
			}
		}
		System.out.println(s);
	}
}

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

int n,d;
string s[222];
set<string>st[222];
bool used[222][222];
set<string>::iterator it,it2;

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin>>n,n){
    memset(used,0,sizeof(used));
    cin>>d;
    r(i,n)cin>>s[i];
    sort(s,s+n);
    r(i,n)st[i].clear();
    r(i,n){
      r(j,s[i].size()){
        string t=s[i];
        t.erase(t.begin()+j);
        st[i].insert(t);
      }
      r(j,s[i].size()+1){
        r(k,26){
          string t=s[i];
          t=t.substr(0,j)+(char)(k+'a')+t.substr(j);
          st[i].insert(t);
        }
      }
      r(j,s[i].size()+1){
        r(k,26){
          string t=s[i];
          t[j]=(char)(k+'a');
          st[i].insert(t);
        }
      }
      r(j,s[i].size()-1){
          string t=s[i];
          swap(t[j],t[j+1]);
          st[i].insert(t);
      }
    }
    int ans=0;
    if(d==1){
      r(i,n)for(int j=i+1;j<n;j++)if(i!=j&&!used[i][j]){{
        for(it=st[i].begin();it!=st[i].end();it++){
            if(s[j]==(*it)){
                used[i][j]=used[j][i]=1;
                cout<<s[i]<<','<<s[j]<<endl;
                ans++;
                break;
            }
          }
        }
      }
    }
    else{
      r(i,n)for(int j=i+1;j<n;j++)if(i!=j&&!used[i][j]){
        for(it=st[i].begin();it!=st[i].end();it++){
              if(st[j].count(*it)){
                used[i][j]=used[j][i]=1;
                cout<<s[i]<<','<<s[j]<<endl;
                ans++;
                break;
              }
          }
      }
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 17576
import sys
input = sys.stdin.readline
 
n,m,k = map(int,input().split())
ab = [set() for _ in range(n)]
cd = [[] * n for _ in range(n)]

 
#Union Find
 
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
 
#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
 
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    unite(a - 1, b - 1)
    ab[a - 1].add(b - 1)
    ab[b - 1].add(a - 1)

for i in range(k):
    c, d = [int(x) for x in input().split()]
    if same(c - 1, d - 1):
        cd[c - 1].append(d - 1)
        cd[d - 1].append(c - 1)

ans = [0] * n

for i in range(n):
    ans[i] = size(i) - 1 - len(cd[i]) - len(ab[i])

print(*ans)




Measured memory_bytes: 117008
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 1000000007
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};


int n,m,l;

int ans;
signed main(){
	int n; 
	cin>>n;
	cout<<n*(n+1)/2-n<<endl;
//sin x=y arcsin y=x
}

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

int main() {
	int64_t n;
	cin >> n;
	vector<int64_t> a(n * 3);
	for (int i = 0; i < n * 3; i++) {
		cin >> a.at(i);
	}
	sort(a.begin(), a.end());
	int64_t ans = 0;
	for (int i = n; i < n * 3; i = i + 2) {
		ans += a.at(i);
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>

using namespace std;

int main(void){

  double m500,m1000;

  while( cin >> m500 >> m1000 ){

    if( m500 < 35.5 && m1000 < 71 ) cout << "AAA" << endl;
    else if( m500 < 37.5 && m1000 < 77 ) cout << "AA" << endl;
    else if( m500 < 40 && m1000 < 83 ) cout << "A" << endl;
    else if( m500 < 43 && m1000 < 89 ) cout << "B" << endl;
    else if( m500 < 50 && m1000 < 105 ) cout << "C" << endl;
    else if( m500 < 55 && m1000 < 116 ) cout << "D" << endl;
    else if( m500 < 70 && m1000 < 148 ) cout << "E" << endl;
    else cout << "NA" << endl;

  }
  return 0;
}

Measured memory_bytes: 1224
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int n = vs[0];
			int k = vs[1];

			int[] h = Console.ReadLine().Split().Select(int.Parse).ToArray();

			int[] dp = new int[n];
			dp[0] = 0;
			dp[1] = Math.Abs(h[0] - h[1]);
			for (int i = 1; i < n; i++) {
				int cost = int.MaxValue;
				for (int j = 1; j <= k; j++) {
					if (i - j >= 0) {
						cost = Math.Min(cost, dp[i - j] + Math.Abs(h[i - j] - h[i]));
					} else {
						break;
					}
				}
				dp[i] = cost;
			}
			Console.WriteLine(dp[n - 1]);

		}
	}
}


Measured memory_bytes: 20064
n = int(input())
S = []
dic = {}
count = 0

for i in range(n):
    S.append(str(sorted(input())))
    
for Sstr in S:
    if Sstr in dic:
        count += dic[Sstr]
        dic[Sstr] += 1
    else:
        dic[Sstr] = 1
        

print(count)

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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> snuke(n, 0);
    int d;
    for(int i = 0; i < k; i++){
        cin >> d;
        int tmp;
        for(int j = 0; j < d; j++){
            cin >> tmp;
            snuke[tmp-1]++;
        }
    }

    int cnt = 0;

    for(int i = 0; i < n; i++){
        if(snuke[i] == 0) cnt++;
    }

    cout << cnt << endl;
}

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

int main(){
    int h, w;
    cin >> h >> w;
    char a[h][w];
    rep(i, h){
        rep(j, w){
            cin >> a[i][j];
        }
    }
    rep(i, w+2) cout << "#";
    cout << endl;
    rep(i, h){
        cout << "#";
        rep(j, w) cout << a[i][j];
        cout << "#" << endl;
    }
    rep(i, w+2) cout << "#";
    cout << endl;
    return 0;
}

Measured memory_bytes: 3524
program taskC;
var
    s, t, c, a : ansistring;
    i : longint;
    pre : boolean;
    
begin
    readln(s);
    a := s;
    t := '';
    pre := true;
    while (pre = true) do
    begin
        pre := false;
        c := copy(a,1,5);
        if (c = 'dream') and (pre = false) and ((length(a) = 5) or (((a[6] = 'e') and (a[8] = 'a')) or (a[6] = 'd'))) then
        begin
            pre := true;
            t := t + c; 
            delete(a,1,5);
        end;
         c := copy(a,1,5);
        if (c = 'erase') and (pre = false) and ((length(a) = 5) or (((a[6] = 'e') and (a[8] = 'a')) or (a[6] = 'd'))) then
        begin
            pre := true;
            t := t + c;
            delete(a,1,5);
        end;
        c := copy(a,1,6);
        if (c = 'eraser') and (pre = false) and ((length(a) = 6) or (((a[7] = 'e') and (a[9] = 'a')) or (a[7] = 'd')))then
        begin
            pre := true;
            t := t + c;
            delete(a,1,6); 
        end;
        c := copy(a,1,7);
        if (c = 'dreamer') and (pre = false) and ((length(a) = 7) or (((a[8] = 'e') and (a[10] = 'a')) or (a[8] = 'd'))) then
        begin
            pre := true;
            t := t + c;
            delete(a,1,7);
        end;
    end;
    if s = t then
    begin
        writeln('YES')
    end
    else 
    begin
        writeln('NO');
    end;
end.



Measured memory_bytes: 1376
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [Usize1; n],
    };

    if k <= n {
        let mut ca = 0;
        for _ in 0..k {
            ca = a[ca];
        }
        println!("{}", ca + 1);
        return;
    }

    let mut c = vec![0; n];
    let mut ca = 0;
    loop {
        c[ca] += 1;
        if c[ca] == 3 {
            break;
        }
        ca = a[ca];
    }
    let mut start_count = 0;
    let mut loop_count = 0;
    for &c_i in c.iter() {
        match c_i {
            0 => {}
            1 => start_count += 1,
            2 => loop_count += 1,
            3 => loop_count += 1,
            _ => unreachable!(),
        }
    }
    let mut ca = 0;
    for _ in 0..start_count {
        ca = a[ca];
    }
    let rk = (k - start_count) % loop_count;
    for _ in 0..rk {
        ca = a[ca];
    }
    let ans = ca + 1;
    println!("{}", ans);
}


Measured memory_bytes: 5752
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int xMax = -200, yMin = 200;
    for(int i = 0; i < n; i++){
        int b;
        cin >> b;
        if(b > xMax){
            xMax = b;
        }
    }
    for(int i = 0; i < m; i++){
        int b;
        cin >> b;
        if(b < yMin){
            yMin = b;
        }
    }
    bool isWar = true;
    for(int i = x+1; i <= y; i++){
        if(i > xMax && i <= yMin){
            isWar = false;
            break;
        }
    }

    cout << (isWar?"War":"No War") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, k; cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));

    ll l = -inf;
    ll r = inf;

    while (l + 1 < r) {
        ll M = (l + r) / 2;
        ll cnt = 0;

        rep(i, n) {
            ll l = i, r = n;
            while (l + 1 < r) {
                ll m = (r + l) / 2;
                if (a[i] * a[m] <= M) {
                    (a[i] > 0 ? l = m : r = m);
                } else {
                    (a[i] > 0 ? r = m : l = m);
                }
            }
            if (a[i] > 0) cnt += l - i;
            else cnt += n - r;
        }

        (cnt < k) ? l = M : r = M; // lまでは cnt < k, rからは k <= cntとなる。
    }

    cout << r << endl;
    return 0;
}

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

vector<int> A;
vector<int> a, b, c, d;

void dfs(int i, int &res, int num, int size, int range_start, int range_end) {
  if (i == size) {
    int tmp = 0;
    for (int j = 0; j < num; j++) {
      if (A[b[j]-1] - A[a[j]-1] == c[j]) tmp += d[j];
    }
    if (tmp > res) res = tmp;
  }
  else {
    for (int j = range_start; j <= range_end; j++) {
      A[i] = j;
      dfs(i+1, res, num, size, j, range_end);
    }
  }
}

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  
  A.resize(N);
  a.resize(Q);
  b.resize(Q);
  c.resize(Q);
  d.resize(Q);
  
  for (int i = 0; i < Q; i++) cin >> a[i] >> b[i] >> c[i] >>d[i];

  int res = 0;
  dfs(0, res, Q, N, 1, M);

  cout << res << endl;
}


Measured memory_bytes: 3508
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<double, double>;

int main() {
    int n;
    cin >> n;
    vector<int> t(n+1, 0);
    vector<double> v(n+2, 0);
    rep(i, n) cin >> t[i+1];
    rep(i, n) cin >> v[i+1];

    rep(i, n)t[i+1] += t[i];
    vector<vector<P>> u(n);
    rep(i, n){
        u[i].push_back(make_pair(1.0, 0.0));
        u[i].push_back(make_pair(-1.0, t[n]));
        rep(j, n){
            if(j < i)u[j].push_back(make_pair(-1.0, v[i+1]+t[i]));
            else if(j==i)u[j].push_back(make_pair(0.0, v[i+1]));
            else u[j].push_back(make_pair(1.0, v[i+1]-t[i+1]));
        }
    }

    ld d = 0;
    double bv = 0.0;
    rep(i, n){
        for(double j = t[i]+0.5; j <= t[i+1]+1e-6; j += 0.5){
            double vv = 10000.0;
            rep(k, n+2)vv = min(vv, u[i][k].first * j + u[i][k].second);
            double dx = (bv + vv) / 4.0;
            bv = vv;
            d += dx;
        }
    }
    cout << setprecision(14);
    cout << d << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;

int n;
ll s[100005];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n;
	vector<ll> a(n+2);
	a[0]=0;
	a[n+1]=0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i-1] + abs(a[i]-a[i-1]);
	}
	s[n+1] = s[n] + abs(a[n+1]-a[n]);
	vector<ll> v(n+1);
	for (int i = 1; i <= n; i++) {
		v[i] = s[n+1] - s[i+1] + s[i-1] + abs(a[i+1]-a[i-1]);
	}
	for (int i = 1; i <= n; i++) cout << v[i] << endl;
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int F[100][10];
ll P[100][11];

int main()
{
  int N;
  cin >> N;

  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < 10; j++)
      cin >> F[i][j];
  }
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < 11; j++)
      cin >> P[i][j];
  }

  ll bene2 = -100000000007;
  for (int i = 1; i < (1 << 10); i++)
  {
    ll bene = 0;
    for (int k = 0; k < N; k++)
    {
      int open = 0;
      for (int j = 0; j < 10; j++)
      {
        if (i & (1 << j) && F[k][j])
          open++;
      }
      bene += P[k][open];
    }
    bene2 = max(bene2, bene);
  }
  cout << bene2 << endl;
  return 0;
}


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

int main () {
  int N , M ;
  cin >> N >> M ;
  
  vector<int> vec(2*M);
  
  for (int i = 0 ; i < 2*M ; i++ ) {
    cin >> vec.at(i) ;
  }
  
  for ( int i = 0 ; i < N ; i++) {
    int sum = 0 ;
    for ( int k = 0 ; k < 2*M ; k++){
      if ( vec.at (k) == i+1 ){
        sum++ ;
      }
    }
    cout << sum << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      	bool Y = false;
      	int N;
      string S;
      
		cin >> N;
        for (int i = 0; i < N; i++)
        {
          cin >> S;
          if (S == "Y")
          {
            Y = true;
          }
        }
      	if (Y == true)
        {
          cout << "Four" << endl;
        }
      else
      {
          cout << "Three" << endl;
      }
     
    }

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

int main(){
  string w;
  cin >> w;
  int ch[26]={};
  for(int i=0; i<w.size(); i++){
    ch[w[i]-'a']++;
  }
  for(int i=0; i<26; i++){
    if(ch[i]%2==1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

int prim() {
    int d[n], p[n];
    int color[n];
    
    for(int i=0; i<n; i++) {
        color[i] = WHITE;
        d[i] = INFTY;
        p[i] = -1;
    }
    
    d[0] = 0;
    
    while(1) {
        int u;
        int mincost = INFTY;
        for (int i=0; i<n; i++) {
            if (color[i] != BLACK && d[i] < mincost) {
                mincost = d[i];
                u = i;
            }
        }
        
        if (mincost == INFTY) break;
        
        color[u] = BLACK;
        
        for (int v=0; v<=n; v++) {
            if (color[v] != BLACK && M[u][v] != INFTY) {
                if(M[u][v] < d[v]) {
                    d[v] = M[u][v];
                    p[v] = u;
                    color[v] = GRAY;
                }
            }
        }
    }
    
    int sum = 0;
    for (int i=0; i<n; i++) {
        if(p[i] != -1) sum += M[i][p[i]];
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int tmp;
            scanf("%d", &tmp);
            M[i][j] = (tmp == -1) ? INFTY : tmp;
        }
    }
    
    int sum = prim();
    printf("%d\n", sum);
    
    return 0;
}


Measured memory_bytes: 2736
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)



int main(){

string s;
cin>>s;
string tar ="hi";
ll ff=1;
for(ll i=0;i<s.size();i++){
    if(i%2==0){
    if(s[i]=='h'){

    }
    else{
        ff=0;
        break;
    }
    }
      if(i%2==1){
    if(s[i]=='i'){

    }
    else{
        ff=0;
        break;
    }
      }
}
if((ll)(s.size())%2==1||ff==0){
cout<<"No"<<endl;
}
else{cout<<"Yes"<<endl;}

}


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

#define ll long long
#define UN unsigned
#define pb push_back
#define mod 1000000007
#define mt make_tuple
typedef tuple<int, int> tii;
typedef pair<int, int> pii;

void solve(){
    ll x;
    cin >> x;

    ll ans = 1000*(x/500);
    x %= 500;

    ans += 5*(x/5);
    cout << ans;
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 256
def solve():
    S = input()
    T = input()
    N = len(S)
    M = 2 * N
    S += S
    nxt = [[M] * 26 for i in range(M + 1)]
    for i in range(M - 1, -1, -1):
        for j in range(26):
            nxt[i][j] = nxt[i + 1][j]
        nxt[i][ord(S[i]) - ord('a')] = i
    ans = 0
    i = 0
    for c in T:
        pos = ord(c) - ord('a')
        if nxt[i][pos] == M:
            return -1
        ans += nxt[i][pos] - i + 1
        i = (nxt[i][pos] + 1) % N
    return ans

print(solve())


Measured memory_bytes: 132884
#include<iostream>
#include<iomanip>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N;
	cin >> N;
	vector<int> A(N), B(N), C(N);
	REP(i, N) {
		cin >> A[i];
		A[i]--;
	}
	REP(i, N) cin >> B[i];
	REP(i, N - 1) cin >> C[i];
	int res = B[A[0]];
	REP(i, N - 1) {
		res += B[A[i + 1]];
		if (A[i + 1] == A[i] + 1) res += C[A[i]];
	}

	cout << res << endl;

	return 0;
}


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

int main() {
  int k,n,m,l;
  cin >> k >> n;  
  vector<int>a(n);
  vector<int>b(n);
  for(int i=0;i<n;i++){
  cin >> a.at(i);  
  } 
  for(int i=0;i<n;i++){
    if(i==0){
    b.at(i)=k-a.at(n-1)+a.at(0);  
    } 
    else{
    b.at(i)=a.at(i)-a.at(i-1);
    }  
  } 
  sort(b.begin(),b.end());
  cout << k-b.at(n-1) << endl; 
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define RI(x) x = rit()
#define RII(a,b) a = rit(), b = rit()
#define RIII(a,b,c) a = rit(), b = rit(), c = rit()
#define REP(I, N) for(int I=0;I<int(N);I++)
#define REPP(I, N) for(int I=1;I<=int(N);I++)
inline int rit(){
    int f=0,key=1;
    char ch;
    do{
        ch = getchar();
        if(ch=='-') key=-1;;
    }while(ch<'0'||ch>'9');
    do{
        f = f*10+ch-'0';
        ch = getchar();
    }while(ch>='0'&&ch<='9');
    return f*key;
}
using namespace std;
int main(void){
    int k,s,ans=0;
    RII(k,s);
    REP(i,k+1) REP(j,k+1){
        if(i+j<=s&&s-i-j<=k) ans++;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
char ch;
int t[501][501],dp[501][501],ph[501][501],pw[501][501],H,W,n,mx,mnh,lmx,a;
void init(){
  for(int j=1;j<=H;j++){
    for(int k=1;k<=W;k++){
      cin>>ch;
      if(ch=='.')a=1;
      if(ch=='*')a=0;
      t[j][k]=a;
    }
  }
  mx=0;
  for(int i=0;i<=H;i++){
    t[i][0]=t[0][i]=0;
    for(int j=0;j<=W;j++){
      dp[i][j]=ph[i][j]=pw[i][j]=0;
    }
  }
}
int main(){
  
  while(1){
    cin>>H>>W;
    if(H==0&&W==0)break;
    init();
    for(int i=1;i<=H;i++){
      for(int j=1;j<=W;j++){
	if(t[i][j]==0){dp[i][j]=ph[i][j]=pw[i][j]=0;continue;}
	ph[i][j]=ph[i-1][j]+1;   pw[i][j]=pw[i][j-1]+1;

	lmx=0;mnh=100;
	for(int k=0;k<pw[i][j];k++){
	  if(mnh>=ph[i][j-k])mnh=ph[i][j-k];
	  if(lmx<mnh*(k+1))lmx=mnh*(k+1);
	}
	dp[i][j]=lmx;
	

	if(mx<dp[i][j])mx=dp[i][j];
      }
    }
    /*
	for(int x=1;x<6;x++){
	  for(int y=1;y<6;y++){
	    cout<<dp[x][y];
	  }
	  cout<<endl;
	  }*/
    cout<<mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 5084
# include <bits/stdc++.h>
# define int long long
# define endl "\n"
using namespace std;

void solve() {

	char a;
	cin >> a;

	if (isupper(a)) {
		cout << "A";
	}
	else {
		cout << "a";
	}
}

signed main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

# ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
# endif

	solve();

	return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
typedef long long ll;
const int mod=1000000007;
int mul(int a,int b){return(ll)a*b%mod;}
int p[610],c[610][610],f[610][610],g[610];
int main(){
	int n,m,i,j,k,x,y,t,s;
	bool flag;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		p[x]=y;
		p[y]=x;
	}
	n<<=1;
	g[0]=1;
	for(i=2;i<=n;i+=2)g[i]=mul(g[i-2],i-1);
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++)c[i][j]=c[i][j-1]+!p[j];
	}
	s=0;
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			flag=0;
			for(k=i;k<=j;k++){
				if(p[k]&&(p[k]<i||p[k]>j)){
					flag=1;
					break;
				}
			}
			if(flag)continue;
			t=g[c[i][j]];
			for(k=i+1;k<j;k++)(t-=mul(f[i][k],g[c[k+1][j]]))%=mod;
			f[i][j]=t;
			(s+=mul(f[i][j],g[n-m*2-c[i][j]]))%=mod;
		}
	}
	printf("%d",(s+mod)%mod);
}

Measured memory_bytes: 3072
from sys import exit, stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for n in range(N)]
B = [stdin.readline().rstrip() for m in range(M)]
for i in range(N-M+1):
  for j in range(N-M+1):
    tmp = [a[j:j+M] for a in A[i:i+M]]
    if tmp == B:
      print('Yes')
      exit()
print('No')

Measured memory_bytes: 39152
#include <bits/stdc++.h>
using namespace std;
string s;
bool b[30];
int main() {
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        b[s[i] - 'a'] = 1;
    }
    for (int i = 0; i < 26; ++i) {
        if (!b[i]) {
            cout << (char)('a' + i) << endl;
            return 0;
        }
    }
    puts("None");
    return 0;
}


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

int n, m, q;
vector<int> a, b, c, d;
int ans = 0;
void dfs(vector<int> k){
  if((int)k.size() == n){
    int sco = 0;
    for(int i = 0; i < q; i++){
      if(k.at(b.at(i)-1) - k.at(a.at(i)-1) == c.at(i)) sco += d.at(i);
    }
    ans = max(ans, sco);
    return;
  }
  
  k.push_back(k.back());
  while(k.back() <= m){
    dfs(k);
    k.back()++;
  }
}

int main(){
  cin >> n >> m >> q;
  a = b = c = d = vector<int> (q);
  for(int i = 0; i < q; i++) cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
  
  vector<int> sam(1, 1);
  dfs(sam);
  cout << ans << endl;
}

Measured memory_bytes: 3640
#include <iostream>
#include <map>

using namespace std;

int main(void) {
  int N;
  std::cin >> N;
  map<int, int> imap;
  int cnt = 0;
  for (int i = 1; i < N; ++i) {
    if (imap.find(N - i) != imap.end())
      continue;
    if (imap.find(i) != imap.end())
      continue;
    if (N - i == i)
      continue;

    imap[i] = N - i;
    ++cnt;
  }
  cout << cnt  << endl;
  
  return 0;                                                                                            
}

Measured memory_bytes: 23680
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) x.begin(), x.end()
using namespace std;
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=50000;i++){
    if(i*108/100==n){
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<":("<<endl;
}

Measured memory_bytes: 3644
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

count = 0
antena = [a,b,c,d,e]

for i in antena:
    for j in antena:
        if abs(i - j) <= k:
            count += 1

if count == 25:
    print("Yay!")
else:
    print(":(")


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>

/*
なんでWAナノカ本当にわからん
*/

using ll = long long;

#define onWall(x, y) (x % r == 0 || y % c == 0)

using namespace std;

using P = pair<int, int>;
#define fi first
#define se second

int main() {
    int r, c, n;
    cin >> r >> c >> n;
    vector<int> wall;
    P points[200000];
    for (int i=0, x1, x2, y1, y2; i<n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        points[i] = {x1, y1};
        points[i+n] = {x2, y2};
        if (onWall(x1, y1) && onWall(x2, y2)) {
            wall.push_back(i);
            wall.push_back(i+n);
        }
    }
    auto to_line = [&](P p){
        int x = p.fi, y = p.se;
        if (y==0) return x;
        if (x==r) return r+y;
        if (y==c) return r+c+r-x;
        return r+c+r+c-y;
    };
    sort(wall.begin(), wall.end(), [&](int a, int b) {
        P ap = points[a], bp = points[b];
        return to_line(ap) < to_line(bp);
    });
    stack<int> st;
    for (auto w:wall) {
        cerr << points[w].fi << ' ' << points[w].se << ' ' << w % n << '\n';
        w %= n;
        if (!st.empty() && w == st.top()) st.pop();
        else st.push(w);
    }
    cout << (st.empty() ? "YES" : "NO") << '\n';
    return 0;
}

Measured memory_bytes: 2936
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

bool check(int i){
  bool retval = true;
  for (int j=2; j<=sqrt(i); j++){
    if (i%j==0){
      retval = false;
      break;
    }
  }
  return retval;
}

int main(){
  int X;
  scanf("%d", &X);
  int i = X;
  while(!check(i)){
    i++;
  }
  printf("%d\n",i);
  return 0;
}


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

using namespace std;


int main() {
 long long int a,b,c,d[100010],e[100010];
  
  cin >> a >> b >> c;
  
  for(int i=0;i<a;i++){
    e[i] = 0;
  }
  
  for(int i=0;i<c;i++){
    cin >> d[i];
    
    e[d[i]-1]++;
  }
  
 
  
  for(int i=0;i<a;i++){
    
    if(b+e[i]-c >0){
      cout << "Yes" << endl;
    }
    
    else {
     cout << "No" << endl;
    }
  }
  
}


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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main() {
  int N,H;
  cin>>N>>H;
  vector<pair<int,int>> v;
  for(int i(0);i<N;i++){
    int a,b; 
    cin>>a>>b;
    v.push_back({a,0});
    v.push_back({b,1});
  }
  sort(v.rbegin(),v.rend());
  int cnt(0);
  int index(0);
  while(H > 0){
    //coIut << H << endl;
    if(v[index].second == 1){
      cnt++;
      H -= v[index].first;
      index++;
    }else{
      cnt += (H+v[index].first-1)/v[index].first;
      cout << cnt << endl;
      return 0;
    }
    //cout << cnt << endl;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    ll n;
    string s = "";
    cin >> n;
    if (n == 0) {
        s += "0";
        reverse(s.begin(), s.end());
        cout << s << endl;
        return 0;
    }

    for (int i = 1; i < 100000; i += 2) {
        if (n % (ll)pow(2, i) == 0) {
            s += "0";
        }
        else {
            s += "1";
            
            n -= pow(2, i-1);
        }
        if (n == 0) {
            reverse(s.begin(), s.end());
            for (int j = 0; j < s.size(); j++) {
                if (j == 0 && s[j] == '0') {
                    continue;
                }
                cout << s[j];
            }
            cout << endl;
            return 0;
        }

        if (n % (ll)pow(2, i+1) == 0) {
            s += "0";
        }
        else {
            s += "1";
            n += pow(2, i);
        }
    }
}

Measured memory_bytes: 256
# A = [list(map(int, input().split())) for _ in range(3)]
# X = int(input())
# B = [int(input()) for _ in range(n)]
# A = list(map(int, input().split()))
k, n = map(int, input().split())
A = list(map(int, input().split()))
A.append(A[0]+k)
diff = 0
for i in range(n):
    diff = max(A[i+1]-A[i], diff)
print(k-diff)


Measured memory_bytes: 26420
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  struct comp {
    bool operator()(pii a, pii b) {
      if (a.first != b.first) return a.first > b.first;
      return a.second > b.second;
    }
  };
  int n;
  while (cin >> n, n) {
    priority_queue<pii, vector<pii>, comp> pq;
    while (n--) {
      int m, a, b;
      cin >> m >> a >> b;
      pq.emplace(a, m);
      pq.emplace(b, -m);
    }
    int w = 0;
    while (pq.size()) {
      w += pq.top().second;
      pq.pop();
      if (w > 150) {
        cout << "NG" << endl;
        goto next;
      }
    }
    cout << "OK" << endl;
  next:;
  }
}

Measured memory_bytes: 3012
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[5];
        for (int i = 0 ; i < 5 ; i++) {
a[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        for (int i = 0 ; i < 5 ; i++) {
            for (int j = 0 ; j < 5 ; j++) {
                if (i < j) {
                    if (Math.abs(a[i] - a[j]) > k)  {
                        System.out.println(":(");
                        return;
                    }
                }
            }
        }
        System.out.println("Yay!");





    }

}

Measured memory_bytes: 23380
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
  int N;
  scanf("%d", &N);
  int A[1000001];

  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }
  sort(A, A+N);

  int temp = A[0];
  int res = 1, count = 0;
  for (int i = 1; i < N; i++) {
    if (temp == A[i]) {  // res = 1からスタート偶数個なら消す
      res++;
      res = res % 2;
    }
    else {
      temp = A[i];
      count += res;
      res = 1;
    }
  }
  count += res;

  printf("%d\n", count);

  return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

bool is_integer(double A){
    if(floor(A) == A){
        return true;
    }
    else{
        return false;
    }
}

//10:35
int main()
{
    string s;
    cin >> s;
    if(s == "Sunny"){
        cout << "Cloudy" << endl;
    }
    else if(s == "Cloudy"){
        cout << "Rainy" << endl;
    }
    else{
        cout << "Sunny" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int w,a,b;
	 
	cin>>w>>a>>b;
	
	if(b<=a)
	cout<<max(0,a-b-w);
	else
	cout <<max(0,b-a-w);
	return 0;
}


Measured memory_bytes: 256
N=int(input())
Ls=list(map(int, input().split()))
Ls = sorted(Ls, reverse=True)
Lmax=Ls[0]
Lsum=0
for i in range(1,N):
    Lsum+=Ls[i]
if Lmax < Lsum:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    vector <long long> a(n+1,0),b(n+1,0),c(n+1,0);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<n;i++)
        cin>>c[i];
    long long sum=0;
    for(int i=1;i<n;i++)
    {
        sum+=b[a[i]];
        if(a[i]==a[i+1]-1)
        sum+=c[a[i]];
    }
    sum+=b[a[n]];
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
N = gets.to_i
AN = gets.split.map(&:to_i)
BC = gets.chomp.to_i.times.map { gets.split.map(&:to_i) }

sum = AN.sum
counts = AN.group_by(&:itself).to_h { |k, v| [k, v.count] }
# counts = AN.tally
# counts.default = 0

BC.each do |bc|
  b, c = bc
  counts[b] ||= 0
  counts[c] ||= 0
  sum = sum + (c - b) * counts[b]
  counts[c] = counts[c] + counts[b]
  counts[b] = 0
  puts sum
end


Measured memory_bytes: 32920
/* 

	 - If you fail to prepare, you are prepared to fail.	

	(C) Mark Spitz

*/

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define S second
#define F first
#define all(x) (x).begin(), (x).end()

using namespace std;
using ll = long long;

void setIO(string name = "") {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 5;

int n;
int d[MAXN][2];	
int a[MAXN];

void solve() {
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> d[i][0] >> d[i][1];
		a[i] = d[i][0] - d[i][1];
	}
	
	for (int i = 1; i <= n - 2; i++) {
		if (a[i] == 0 && a[i + 1] == 0 && a[i + 2] == 0) {
			cout << "Yes";
			return;
		}
	}
	
	cout << "No";
}

main() {
	setIO();
	
	int tt = 1;
	//~ cin >> tt;
	while (tt--) {
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 3656
import java.io.IOException;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
             
       Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      
      if(a<b){
    	  System.out.println("a < b");
      }
      
      if(a>b){
    	  System.out.println("a > b");
      }
      if(a==b){
          System.out.println("a == b");
    
      } 
    }
}

Measured memory_bytes: 17320
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
vector<int> A, B,C;
string S, T;

void input() {
  int x, y, z;
  cin>>N;
  A.resize(N);
  B.resize(N);
  C.resize(N);
  rep(i,0,N-1){
    cin>>x;x--;
    A[i]=x;
  }
  rep(i,0,N-1){
    cin>>B[i];
  }
  rep(i,0,N-1){
    cin>>C[i];
  }
  ;
}
void solve() {
  int ans=0;
  ans = B[A[0]];
  int prev=A[0];
  rep(i,1,N-1){
    if (prev+1 == A[i]){
      ans += C[prev];
    }
    prev=A[i];

    ans += B[A[i]];



  }
  cout<<ans<<endl;

  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

int main() {
  int n,d;
  cin>>n>>d;
  vector<vector<int>> x(n,vector<int>(d));
  double distance=0;
  int check_distance=0;
  int count=0;
  
  for(int i=0;i<n;i++){
    for(int j=0;j<d;j++){
      int a;
      cin>>a;
      x.at(i).at(j)=a;
    }
  }
  
  for(int i=0;i<n;i++){
    for(int k=0;k<n;k++){
      if(i>=k)continue;
      distance=0;
      check_distance=0;
      for(int j=0;j<d;j++){
        distance+=pow(fabs(x.at(i).at(j)-x.at(k).at(j)),2);
      }
      distance=sqrt(distance);
      check_distance=distance;
      if(distance==check_distance) count++;
    }
   
  }
  cout<<count<<endl;
}


Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn coef(list: &Vec<i32>, reverse: bool) -> Vec<i32> {
    
    let mut ret = Vec::new();
    let n = list.len();
    
    if n % 2 == 0 {
        
        for i in 0..n {
            
            if i == 0 {
                
                ret.push(1);
            } else if i == n - 1 {
                
                ret.push(-1);
            } else if i % 2 != 0 {
                
                ret.push(-2);
            } else {
                
                ret.push(2);
            }
        }
    } else {
        
        for i in 0..n {
            
            if i == 0 || i == n - 1 {
                
                ret.push(1);
            } else if i % 2 != 0 {
                
                ret.push(-2);
            } else {
                
                ret.push(2);
            }
        }
    }
    
    if reverse {
        
        let mut rev = Vec::new();
        for v in ret {
            
            rev.push(v - v * 2);
        }
        
        return rev;
    }
    
    ret
}

fn main() {
    
    let n: i32 = read();
    
    let mut a = Vec::new();
    
    for _x in 0..n {
        
        let b: i32 = read();
        a.push(b);
    }
    
    a.sort();
    
    let mut test1 = coef(&a, false);
    let mut test2 = coef(&a, true);
    
    test1.sort();
    test2.sort();
    
    let mut res1: i64 = 0;
    let mut res2: i64 = 0;
    
    for i in 0..n {
        
        res1 += (a[i as usize] * test1[i as usize]) as i64;
    }
    
    for i in 0..n {
        
        res2 += (a[i as usize] * test2[i as usize]) as i64;
    }
    
    println!("{}", std::cmp::max(res1, res2));
}


Measured memory_bytes: 6396
import sys
sys.setrecursionlimit(10**6)
edges, vertices = map(int, input().split())
dp = [None for _ in range(edges)]

nodes = [[] for _ in range(edges)]

for i in range(vertices):
    start, end = map(int, input().split())
    nodes[end -1].append(start-1)

def find(arr):
    if not len(arr):
        return 0
    for x in arr:
        if dp[x] is None:
            dp[x] = find(nodes[x])
    return 1 + max(dp[x] for x in arr)

for i in range(edges):
    dp[i] = find(nodes[i])

print(max(dp))


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

using namespace std;

#define sqr(x) ((x) * (x))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

typedef vector<int> vi;
typedef long long ll;

void solve() {
  int N;
  cin >> N;
  vector<vector<pair<int, int>>> xy(N);
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    xy[i].resize(A);
    for (int j = 0; j < A; j++) {
      cin >> xy[i][j].first >> xy[i][j].second;
    }
  }
  int ans = 0;
  for (int bits = 0; bits < (1 << N); bits++) {
    int cnt = 0;
    bool flag = true;
    for (int i = 0; i < N; i++) {
      if ((bits >> i) & 1) {
        for (int j = 0; j < xy[i].size(); j++) {
          if (xy[i][j].second != ((bits >> xy[i][j].first - 1) & 1)) {
            flag = false;
          }
        }
        cnt++;
      }
    }
    if (flag) ans = max(ans, cnt);
  }
  cout << ans << endl;
}

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

  solve();

  return 0;
}


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

int main(){
	int K;
	int A;
	int B;
	cin>>K;
	cin>>A;
	cin>>B;
	for(int i=A; i<=B; ++i){
		if(i%K==0){
			cout<< "OK" <<endl;
			return 0;
		}
	}
	cout<< "NG" <<endl;

	// int ans = 0;
	// cout<< ans <<endl;
	// cout<<cout<<setprecision(10)<<ans<<endl;
	// printf("%f\n",ans);
}


Measured memory_bytes: 3632
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sin = new Scanner(System.in);
		
		int S, s, m, h;
		S = sin.nextInt();
		s = S % 60 ;
		h = (int)(S / 3600);
		m = (int)((S / 60) - (60 * h)) ;
		System.out.println(h +":"+ m + ":" + s);
	}
}


Measured memory_bytes: 26184
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

int main() {
	ll n;
	vector<ll> v[3];
	ll ans = 0;

	cin >> n;

	REP(i, 3) {
		REP(j, n) {
			ll x;
			cin >> x;
			v[i].push_back(x);
		}
	}

	REP(i, 3) {
		sort(v[i].begin(), v[i].end());
	}

	REP(i, n) {
		vector<ll>::iterator it1 = lower_bound(v[0].begin(), v[0].end(), v[1][i]);
		vector<ll>::iterator it2 = upper_bound(v[2].begin(), v[2].end(), v[1][i]);

		ans += (distance(v[0].begin(), it1)) * distance(it2, v[2].end());
	}

	cout << ans << endl;
}

Measured memory_bytes: 3444
use proconio::input;
use proconio::marker::Chars;
use std::io::Write;

pub trait Echo {
    fn echo(&self);
    fn echo_b(&self, out: &mut std::io::Stdout) -> Result<(), std::io::Error>;
}

macro_rules! impl_echo {
    ($($t:ty),*) => {
        $(
            impl Echo for $t {
                fn echo(&self){
                    self.echo_b(&mut std::io::stdout()).unwrap();
                }

                fn echo_b(&self, out: &mut std::io::Stdout) -> Result<(), std::io::Error>{
                    writeln!(out,"{}", &self)?;
                    Ok(())
                }
            }
        )*
    };
}

macro_rules! impl_echo_f {
    ($($t:ty),*) => {
        $(
            impl Echo for $t {
                fn echo(&self){
                    self.echo_b(&mut std::io::stdout()).unwrap();
                }

                fn echo_b(&self, out: &mut std::io::Stdout) -> Result<(), std::io::Error>{
                    writeln!(out,"{:.12}", &self)?;
                    Ok(())
                }
            }
        )*
    };
}

impl_echo!(u8, u16, u32, u64, u128, usize);
impl_echo!(i8, i16, i32, i64, i128, isize);
impl_echo!(&str, String, char);
impl_echo_f!(f32, f64);

impl<T: Echo> Echo for Vec<T> {
    fn echo(&self) {
        self.echo_b(&mut std::io::stdout()).unwrap();
    }
    fn echo_b(&self, out: &mut std::io::Stdout) -> Result<(), std::io::Error> {
        for i in self {
            i.echo_b(out).unwrap();
        }
        Ok(())
    }
}

fn main() {
    input! {
        s: Chars,
        t: Chars
    };
    let len = s.len();
    let same = (0..len).filter(|i| s[*i] == t[*i]).count();
    let res = len - same;
    res.echo();
}


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

int main(){
	int i,j,k,l,n,m,c,z;
	cin >> n >> z;
	long long x[n],y[n],a[n],b[n],ans=5000000000000000000;
	for(i=0;i<n;i++){
		cin >> x[i] >> y[i];
		a[i] = x[i];
		b[i] = y[i];
	}
	sort(x,x+n);
	sort(y,y+n);
	for(i=0;i<n;i++){
		for(j=i;j<n;j++){
			for(k=0;k<n;k++){
				for(l=k;l<n;l++){
					c = 0;
					for(m=0;m<n;m++){
						if(x[i]<=a[m] && a[m]<=x[j] && y[k]<=b[m] && b[m]<=y[l]){
							c++;
						}
					}
					if(c>=z){
					ans = min(ans,(x[j]-x[i])*(y[l]-y[k]));
					}
				}
			}
		}
	}
	cout << ans << endl;
}

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

string gyaku(string s){
  string n="";
  for(int i=0;i<s.size();i++){
    n=n+s[s.size()-i-1];
  }
  return n;
}

int main() {
  string S;cin>>S;
  S=gyaku(S);
  vector<string> T(4);
  T={"dream","dreamer","erase","eraser"};
  for(int i=0;i<T.size();i++)T[i]=gyaku(T[i]);
  int now=0,znow=0;
  string ans="YES";
  while(now<S.size()){
    for(int i=0;i<T.size();i++){
      if(S.substr(now,T[i].size())==T[i])now+=T[i].size();
    }
    if(znow==now){
      ans="NO";
      break;
    }
    znow=now;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 968
N = int(input())
Tl, Al = map(int, input().split())
for i in range(N-1):
    Tr, Ar = map(int, input().split())
    k = max((Tl-1)//Tr, (Al-1)//Ar) + 1
    Tl, Al = k * Tr, k * Ar

print(Tl+Al)

Measured memory_bytes: 3060