akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_in(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef int64_t ll;


vector<int> si;
int root(int i){
  if(si[i]==i) return i;
  return si[i]=root(si[i]);
}

bool solve() {
  int n;long m;int q;
  cin>>n>>m>>q;
  vector<int> a(q),b(q),c(q);
  rep(i,q){
    cin>>a[i]>>b[i]>>c[i];
  }

  rep(i,n){
    si.push_back(i);
  }

  int islands=n;
  rep(i,q){
    if(c[i]!=0) continue;
    int ra=root(a[i]);
    int rb=root(b[i]);
    if(ra!=rb) {
      si[ra]=rb;
      islands--;
    }
  }

  int doubles=0;
  rep(i,q){
    if(c[i]!=1) continue;
    doubles++;
    int ra=root(a[i]);
    int rb=root(b[i]);
    if(ra==rb) return false;
  }

  if(doubles>0&&m==n-1) return false; // 輪を作るのにエッジが足りない
  //if(doubles>0&&islands<3) return false; // 輪を作るのにノードが足りない
  if(m>(n-1)+((long)islands*(islands-1)/2-(islands-1))) return false;
  return true;
}

int main() {
  cout << (solve()?"Yes":"No") << endl;
}


Measured memory_bytes: 2044
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

bool dp[100005];

signed main()
{
    string s; cin>>s;
    int N=s.size();

    dp[0]=true;
    REP(i,N){
        if(!dp[i]) continue;
        if(i+5<=N and s.substr(i,5)=="dream") dp[i+5]=true;
        if(i+7<=N and s.substr(i,7)=="dreamer") dp[i+7]=true;
        if(i+5<=N and s.substr(i,5)=="erase") dp[i+5]=true;
        if(i+6<=N and s.substr(i,6)=="eraser") dp[i+6]=true;
    }
    cout<<(dp[N]? "YES":"NO")<<endl;
    
}


Measured memory_bytes: 512
#include<stdio.h>
int main(){
int n,m,a,b;
scanf("%d %d",&n,&m);
int min=0;
int max=n;
int ans;
for(int i=0;i<=m;i++){
scanf("%d %d",&a,&b);
if(a<=max&&a>=min){
min=a;
}
else if(a>max){
printf("0");
return 0;
}
else{
}
if (b<max){
max=b;
}
else if(b<min){
printf("0");
return 0;
}
else{
}
}
ans=max-min+1;
printf("%d",ans);
return 0;
}

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

int main()
{
    int h, w;

    while (true) {
        cin >> h >> w;

        if (h == 0 && w == 0) {
            return 0;
        }

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i == 0 || i == h - 1 || j == 0 || j == w - 1) {
                    cout << '#';
                } else {
                    cout << '.';
                }
            }
            cout << endl;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main() {
    long long int d, n;
    cin >> d >> n;
    if(n == 100) {
        cout << (long long int)(pow(100, d) * n + pow(100, d)) << endl;
    } else {
        cout << (long long int)(pow(100, d) * n)<< endl;
    }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        long n = sc.NextLong();
        long m = sc.NextLong();

        long answer = 0;
        for (long i = 1; i * i <= m; i++)
        {
            if (m % i != 0)
            {
                continue;
            }
            long div = m / i;
            if (i >= n)
            {
                answer = Math.Max(answer, div);
            }
            if (div >= n)
            {
                answer = Math.Max(answer, i);
            }
        }

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 27400
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#define REP(i,n) for(int i = 0; i < (int)n; i++)
using namespace std;

int main(){
  long x,t;
  cin >> x >> t;
  cout << max(x-t,(long)0) << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <deque>
#include <iomanip>
using namespace std;

#define ll long long
#define ld long double
#define M_PI 3.14159265358979323846264338327950288
const int N = 998244353;

void solve() {
    ld a, EPS = 1e-10, an = 0;
    cin >> a;

    a = a / 180 * M_PI;

    ld x = 0, y = 0;
    int k = 0;

    do {
        an += a;
        x += cos(an);
        y += sin(an);
        ++k;
    } while (abs(x) + abs(y) > EPS);
    cout << k << endl;
}

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

Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

//素数判定
//#include <cmath>
bool is_prime(long long n) {
	if (n == 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	for (long long i = 3; i <= sqrt(n); i += 2) {
		if (n % i == 0) return false;
	}
	return true;
}

//a^n mod p
//n > 0
//#include <cmath>
long long modpow(long long a, long long n, long long p) {
	a %= p;
	if (a == 0) return 0;
	if (a == 1) return 1;
	long long b = 1, cnt = 0;
	while (b < p && cnt < n) {
		b *= a;
		cnt++;
	}
	if (b < p) return b;
	b %= p;
	return modpow(b, n / cnt, p) * (long long)pow(a, n % cnt) % p;
}

//モジュラ逆数
long long modinv(long long n, long long p) {
	long long a = p, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= p;
	if (u < 0) u += p;
	return u;
}

int main() {
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll n;
	cin >> n;
	vll a(n);
	for (ll i = 0; i < n; i++) cin >> a[i];

	map<ll, ll> lcm;
	vector<map<ll, ll>> v(n);
	for (ll i = 0; i < n; i++) { // a[i] を素因数分解
		ll x = a[i];
		if (x % 2 == 0) {
			ll cnt = 0;
			while (x % 2 == 0) {
				x /= 2;
				cnt++;
			}
			v[i][2] += cnt;
			lcm[2] = max(lcm[2], v[i][2]);
		}
		for (ll j = 3; j <= x; j += 2) {
			if (is_prime(x)) {
				v[i][x]++;
				lcm[x] = max(lcm[x], v[i][x]);
				break;
			}
			if ((x % j) || !is_prime(j)) continue;
			ll cnt = 0;
			while (x % j == 0) {
				x /= j;
				cnt++;
			}
			v[i][j] += cnt;
			lcm[j] = max(lcm[j], v[i][j]);
		}
	}

	ll ans = 1;
	for (auto i = lcm.begin(); i != lcm.end(); i++) {
		ans *= modpow((i -> first), (i -> second), p);
		ans %= p;
	}

	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		sum += modinv(a[i], p);
		sum %= p;
	}

	cout << ans * sum % p << endl;
}


Measured memory_bytes: 3968
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int n, m, l;
    int[][] a, b;
    int i, j, k;
    long[][] c;

    n = sc.nextInt();
    m = sc.nextInt();
    l = sc.nextInt();
    a = new int[n][m];
    b = new int[m][l];
    c = new long[n][l];

    for(i = 0;i < n;i++){
      for(j = 0;j < m;j++){
        a[i][j] = sc.nextInt();
      }
    }
    for(i = 0;i < m;i++){
      for(j = 0;j < l;j++){
        b[i][j] = sc.nextInt();
      }
    }

    for(i = 0;i < n;i++){
      for(j = 0;j < l;j++){
        c[i][j] = 0;
        for(k = 0;k < m;k++){
          c[i][j] += (a[i][k] * b[k][j]);
        }
      }
    }

    for(i = 0;i < n;i++){
      j = 0;
      System.out.print(c[i][j]);
      for(j = 1;j < l;j++){
        System.out.print(" " + c[i][j]);
      }
      System.out.println();
    }

/*fin*/
    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 45348
#include <stdio.h>

int main()
{
    char s[100];
    scanf("%s", s);

    bool boo = true;

    for (int i = 0; i < 100; i++)
    {
        if (s[i] == '\0')
        {
            break;
        }
        if (i % 2 != 0)
        {
            if (s[i] == 'R')
            {
                boo = false;
                break;
            }
        }
        else
        {
            if (s[i] == 'L')
            {
                boo = false;
                break;
            }
        }
    }
    if (boo == false)
    {
        printf("%s\n", "No");
    }
    else
    {
        printf("%s\n", "Yes");
    }

    return 0;
}

Measured memory_bytes: 256
#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 << a*b << endl;
  else if(a*b>c*d) cout <<a*b << endl;
  else cout << c*d<< endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace test
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] lines = Console.ReadLine().Split(' ');

            int x = int.Parse(lines[0]);
            int y = int.Parse(lines[1]);


            for (int i = 0; i < x+1; i++)
            {
                if (i * 2 + (x - i) * 4 == y)
                {
                    //Console.WriteLine(i);
                    Console.WriteLine("Yes");
                    return;
                }

                    

            }

            Console.WriteLine("No");
            return;

        }
    }
}


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

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<pair<long long,long long> > vpll;
typedef vector<vector<pair<ll,ll> > > vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;

#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) x.begin() , x.end()
#define pb push_back
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define left (node << 1)
#define right (node << 1) + 1
#define pii pair<int,int> 
#define mii map<int,int>
#define vi vector<int>
#define umii unordered_map<int,int>
#define mod 998244353
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<": " <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl

#define repo(i,o,e) for(int i = o ; i < e ; i++)
#define rep(n) for(int i = 0 ; i < n ; i++)
const ll sz = 2e5+5;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void solve(){
   int n , m;
   cin >> n >> m;
   int L[m] , R[m];
   int x = INT_MIN, y = INT_MAX;
   rep(m){
        cin >> L[i] >> R[i];
        x = max(x,L[i]);
        y = min(y,R[i]);
   }
   if(y < x){
    cout << 0 << endl;
   }
   else {
    cout << y-x + 1 << endl;
   }

}

int main(){
    FIO;
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

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

using namespace std;
using ll = long long;

int main() {
    string s;
    cin >> s;

    if (s.at(2) == s.at(3) && s.at(4) == s.at(5)) cout << "Yes" << endl;
    else cout << "No" << endl;
    

    return 0;
}

Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int n , k ;
bool bad[30] ;

inline bool ok (int x) {
	while (x) {
		int dig = x % 10 ;
		if (bad[dig]) return 0 ;
		x /= 10 ;
	}
	return 1 ;
}

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

	cin >> n ;

	cin >> k ;
	while (k --) { int x ; cin >> x ; bad[x] = 1 ; }

	while (1) {
		if (ok(n)) return cout << n << '\n' , 0 ; 
		n ++ ;
	}
}


Measured memory_bytes: 384
def cost(s):
  lens = len(s)
  if lens == 1:
    return int(s[0]) // 2 + 1
  costs = [cost(x) for x in s]
  costs.sort()
  return sum(costs[:lens // 2 + 1])

n = int(input())
for _ in range(n):
  s = input()
  s = s.replace("][", "],[")
  s = eval(s)
  print(cost(s))



Measured memory_bytes: 10908
//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

ll p[N], q[N];
vector < ll > vec;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    for (int i = 0; i < a; i ++)
        cin >> p[i];
    for (int i = 0; i < b; i ++)
        cin >> q[i];
    ll t;
    for (int i = 0; i < c; i ++)
        cin >> t, vec.push_back(t);
    sort(p, p + a, greater < ll > ());
    sort(q, q + b, greater < ll > ());
    for (int i = 0; i < x; i ++)
        vec.push_back(p[i]);
    for (int i = 0; i < y; i ++)
        vec.push_back(q[i]);
    sort(vec.begin(), vec.end(), greater < ll > ());
    ll ans = 0;
    for (int i = 0; i < x + y; i ++)
        ans += vec[i];
    cout << ans;
    return 0;
}


Measured memory_bytes: 8048
#include <bits/stdc++.h>
#define int long long
#define N 2005
using namespace std;

int h, w;
int L[N][N], R[N][N], U[N][N], D[N][N];
string s[N];
signed main(){
  
  cin>>h>>w;
  
  for(int i=0;i<h;i++) cin>>s[i];
  
  for(int i=0;i<h;i++){
    int cnt = 0;
    for(int j=0;j<w;j++){
      if( s[i][j] == '.' ) cnt++;
      else cnt = 0;
      L[i][j] = cnt;
    }
  }

  for(int i=0;i<h;i++){
    int cnt = 0;
    for(int j=w-1;j>=0;j--){
      if( s[i][j] == '.' ) cnt++;
      else cnt = 0;
      R[i][j] = cnt;
    }
  }
  
  for(int j=0;j<w;j++){
    int cnt = 0;
    for(int i=0;i<h;i++){
      if( s[i][j] == '.' ) cnt++;
      else cnt = 0;
      U[i][j] = cnt;
    }
  }

  for(int j=0;j<w;j++){
    int cnt = 0;
    for(int i=h-1;i>=0;i--){
      if( s[i][j] == '.' ) cnt++;
      else cnt = 0;
      D[i][j] = cnt;
    }
  }
  
  int ans = 0;
  
  for(int i=0;i<h;i++){
    
    for(int j=0;j<w;j++){
      
      if( s[i][j] == '#' ) continue;
      
      int cnt = 1;
      
      if( i != 0 ) cnt += U[i-1][j];
      if( i != h-1 ) cnt += D[i+1][j];
      if( j != 0 ) cnt += L[i][j-1];
      if( j != w-1 ) cnt += R[i][j+1];
      
      ans = max( ans, cnt );
      
    }
    
  }

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


Measured memory_bytes: 129920
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int main(){
	int a,b;
	vector<int> v;
	map<int,int> mp;
	while(cin>>a,cin.ignore(),cin>>b,a||b){
		mp[a]=b;
		v.push_back(b);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int n;
	while(cin>>n)cout<<v.end()-lower_bound(v.begin(),v.end(),mp[n])<<endl;
	return 0;
}

Measured memory_bytes: 1216
# coding: utf-8
# Your code here!

def Floyd_Warshall(dist): 
    num_of_vertices = n
    for k in range(num_of_vertices):
        for i in range(num_of_vertices):
            for j in range(num_of_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k]+ dist[k][j])



"""
以下実行例
"""
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in input().split()]

"""隣接行列の初期化"""
dist = [[float("inf")]*n for _ in [0]*n]
for i in range(n):
    dist[i][i] = 0

e = []
for _ in range(m):
    a,b,t = [int(i) for i in input().split()]
    dist[a-1][b-1] = t
    dist[b-1][a-1] = t
    e.append((a-1,b-1,t))

Floyd_Warshall(dist)

ans = 0
for a,b,t in e:
    if t > dist[a][b]: ans += 1

print(ans)








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

int main(){
  int n; cin >> n;
  string s; cin >> s;
  vector <char> alp(52);
  for(int i = 0; i < 26; i++){
    alp[i] = 65 + i;
  }
  for(int i = 26; i < 52; i++){
    alp[i] = 65 + i - 26;
  }
  
  for(int i = 0; i < s.size(); i++){
    char temp = s[i];
    int t = 0;
    for(int j = 0; j < 26; j++){
      if(temp == alp[j]){
        t = j;
        break;
      }
    }
    t += n;
    s[i] = alp[t];
  }
  cout << s;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using G = vector<vector<int>>;
    
int main(){
    int n;
    cin >> n;
    ll v = 0;
    rep(i,n){
        v += (ll)(n-i) * (1+i);
    }
    
    ll e = 0;
    rep(i,n-1){
        int from, to;
        cin >> from >> to;
        if(from>to){
            swap(from, to);
        }
        e += (ll)from * (n-to+1);
    }
    ll ans = v - e;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
int main(){
    ios::sync_with_stdio(false);
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(m));
    rep(i,n) {
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    const int INF = INT32_MAX;
    int cost_min = INF;
    for(int bits = 0; bits < (1 << n); bits++) {
        int cost = 0;
        vector<int> alg(m,0); 
        rep(i,n) {
            if((bits >> i)&1) {
                cost += c[i];
                rep(j,m) alg[j]+=a[i][j];
            }
        }
        bool ok = true;
        rep(i,m) if(alg[i] < x) ok = false;
        if(ok) chmin(cost_min,cost);
    }
    if(cost_min == INF) cout << -1 << endl;
    else cout << cost_min << endl;
}

Measured memory_bytes: 3660
#include<bits/stdc++.h> 
using namespace std;typedef long long ll;int main(){ll n,k;cin>>n>>k;unordered_set<ll> done;for(int i=0;i<k;i++){ll d;cin>>d;for(int i=0;i<d;i++){ll u;cin>>u;done.insert(u);}}ll ds=done.size();cout<<n-ds<<endl;}

Measured memory_bytes: 3628
#include<stdio.h>

#define NUM 200001

int cmp1(const void *a,const void *b)
{
  return *(int*)a-*(int*)b;
} 

int cmp2(const void *a,const void *b)
{
  return *(int*)b-*(int*)a;
}

int main()
{
  int n,k;
  
  scanf("%d%d",&n,&k);
  
  int a[n];
  int i;
  int count[NUM]={};
  int length=0;
  int ans=0;
  
  for(i=0;i<n;i++)
  {
    scanf("%d",&a[i]);
    count[a[i]]++;
  }
  
  for(i=1;i<NUM;i++)
  {
    if(count[i]!=0)
    {
      length++;
    }
  }
  
  if(length<=k)
  {
    printf("0\n");
    return 0;
  }
  
  qsort(count,NUM,sizeof(int),cmp2);
  qsort(count,length,sizeof(int),cmp1);
  
  for(i=0;i<length;i++)
  {
    while(count[i]!=0)
    {
      count[i]--;
      ans++;
    }
    if(length-1-i==k)
    {
      printf("%d\n",ans);
      return 0;
    } 
  }
}
        

Measured memory_bytes: 2556
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	int N, M;
	cin >> N >> M;
	vector<bool>S(N + 1, false), E(N + 1, false);
	bool ans = false;
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		if (a == 1) {
			S[b] = true;
		}
		if (b == N) {
			E[a] = true;
		}
	}
	for (int i = 0; i < N+1; ++i) {
		if (S[i] && E[i]) {
			ans = true;
		}
	}
	if (!ans)cout << "IM";
	cout << "POSSIBLE" << endl;
	return 0;
}

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

int main(void)
{
	int h,w;
	scanf("%d%d",&h,&w);
	char s[h][w+1],cpy[h][w+1];
	int i;
	for(i=0;i<=h-1;i++)
		{
		fprintf(stderr,"\ni=%d",i);
		scanf("%s",s[i]);
		strcpy(cpy[i],s[i]);
		}
	
	for(i=0;i<=h-1;i++)
		{
		printf("%s\n%s\n",s[i],cpy[i]);
		}
	
	

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=1<<29,MOD=1e9+7;

int main(){
	int n; cin>>n;
	string s; cin>>s;
	int cnt=0;
	string t;
	rep(i,n){
		if(s[i]=='(') cnt++;
		else{
			if(cnt) cnt--;
			else t+='(';
		}
	}
	rep(i,cnt) s+=')';
	cout<<t+s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    long long N,M,ans=0;cin>>N>>M;
    if(N!=0&&M>2){
        long long a = M/2;
        if(N>=a){
            M-=2*a;
            ans+=a;
        } else {
            M-=2*N;
            ans+=N;
        }
    }
    if(M>=4){
        ans+=M/4;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int x;
    int y;
    int tmp;
    scanf("%d %d", &x, &y);
    while (x != 0 || y != 0)
    {
        if (x > y)
        {
            tmp = x;
            x = y;
            y = tmp;
        }
        printf("%d %d\n", x, y);
        scanf("%d %d", &x, &y);
    }
    return 0;
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/02/24  Problem: code-festival-2016-qual-a_c / Link: https://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_c?lang=en  ----- */
/* ------問題------

高橋君は、英小文字のみからなる文字列 s を持っています。 高橋君は s に対して、次の操作をちょうど K 回行います。
s から好きな位置の文字をひとつ選び、その文字を次のアルファベットへ変える。 ただし、z の次のアルファベットは a であるとする。
例えば、aaz の 2 文字目を選んで操作を行うと、aaz → abz となります。 続けて、abz の 3 文字目を選んで操作を行うと、abz → aba となります。
高橋君は、操作をちょうど K 回行った後の s を、辞書順でできるだけ小さくしたいと考えています。 操作をちょうど K 回行った後の s のうち、辞書順で最小のものを求めてください。

-----問題ここまで----- */
/* -----解説等-----


愚直にシュミレーションはできないけど、各文字26単位でしか変わらないので、最後だけmod26で表現すればよい。
400点の基準ってなんなんだろう

----解説ここまで---- */


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

	string S; int K;
	cin >> S >> K;
	string ans;


	FOR(i, 0, SZ(S)) {
		if (S[i] == 'a')continue;
		int diff = 'z' - S[i] + 1;
		if (diff <= K) {
			S[i] = 'a';
			K -= diff;
		}
	}
	int diff = S[SZ(S)-1]-'a';
	if (K)K %= 26;
	diff += K;
	diff %= 26;
	S[SZ(S) - 1] = 'a'+ diff ;

	ans = S;
	cout << ans << "\n";

	return 0;
}


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

int main(){
  int a,b,c;
  set<int> st;
  cin >> a >> b >> c;
  st.insert(a);
  st.insert(b);
  st.insert(c);
  if (st.size()==2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace ABC136
{
    class Program
    {
        static void Main()
        {
            var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(Math.Max(0,input[2] - (input[0] - input[1])));
        }
    }
}


Measured memory_bytes: 13268
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;

long long a[90];

int main()
{
	int N;
	scanf("%d",&N);
	a[0]=2;
	a[1]=1;
	for(int i=2;i<=86;i++)
	{
		a[i]=a[i-1]+a[i-2];
	}
	printf("%lld\n",a[N]);
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long[] a = new long[3 * N];
    for (int i = 0; i < 3 * N; i++) {
      a[i] = sc.nextLong();
    }
    Arrays.sort(a);
    long ans = 0L;
    for (int i = 1; i <= N; i++) {
      ans += a[3 * N - 2 * i];
    }
    System.out.println(ans);
  }
}

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

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

using ll = long long int;
const ll MOD = 1e9 + 7;

int main() {
  int X, Y, A, B, C;
  std::cin >> X >> Y >> A >> B >> C;

  std::vector<ll> red(A), green(B);
  std::priority_queue<ll> none;
  rep(i, A) {
    std::cin >> red[i];
  }
  rep(i, B) {
    std::cin >> green[i];
  }
  rep(i, C) {
    ll r;
    std::cin >> r;
    none.push(r);
  }

  std::sort(red.rbegin(), red.rend());
  std::sort(green.rbegin(), green.rend());

  int x = 0, y = 0;
  std::priority_queue<ll> que;
  for(int i = 0; i < std::min(X, A); ++i) {
    que.push(-red[i]);
    ++x;
  }
  for(int i = 0; i < std::min(Y, B); ++i) {
    que.push(-green[i]);
    ++y;
  }

  ll ans = 0;
  while(x < X) {
    ll r = none.top(); none.pop();
    ++x;
    ans += r;
  }
  while(y < Y) {
    ll r = none.top(); none.pop();
    ++y;
    ans += r;
  }

  while(!none.empty() && !que.empty()) {
    ll r = none.top();
    ll apple = -que.top(); que.pop();
    if(r > apple) {
      apple = r;
      none.pop();
    }
    ans += apple;
  }
  while(!que.empty()) {
    ans += -que.top(); que.pop();
  }

  std::cout << ans << '\n';
}


Measured memory_bytes: 4724
n = gets.to_i

str = 'abcdefghijklmnopqrstuvwxyz'
result = ''
while n > 0
    div, mod = n.divmod(26)
    result = str[mod - 1] + result
    
    n = (div - (mod == 0 ? 1 : 0))
end

puts result

Measured memory_bytes: 14384
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int T;

signed main(){
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<pair<int, pair<ll, ll>>> vl, vr;
        rep(i, N){
            int K; ll L, R;
            cin >> K >> L >> R;
            if(L >= R) vl.pb({ K,{L,R} });
            else vr.pb({ N-K, {R, L} });
        }
        sort(all(vl));
        sort(all(vr));
        
        priority_queue<ll> pq;
        ll ans = 0;
        rep(i, vl.size()){
            if(pq.size() < vl[i].first){
                ans += vl[i].second.first;
                pq.push(vl[i].second.second-vl[i].second.first);
            }
            else{
                if(pq.size() > 0 && vl[i].second.second-vl[i].second.first < pq.top()){
                    ans += vl[i].second.first;
                    pq.push(vl[i].second.second-vl[i].second.first);
                    ans += pq.top();
                    pq.pop();
                }
                else{
                    ans += vl[i].second.second;
                }
            }
        }

        while(!pq.empty()) pq.pop();
        rep(i, vr.size()){
            if(pq.size() < vr[i].first){
                ans += vr[i].second.first;
                pq.push(vr[i].second.second-vr[i].second.first);
            }
            else{
                if(pq.size() > 0 && vr[i].second.second-vr[i].second.first < pq.top()){
                    ans += vr[i].second.first;
                    pq.push(vr[i].second.second-vr[i].second.first);
                    ans += pq.top();
                    pq.pop();
                }
                else{
                    ans += vr[i].second.second;
                }
            }
        }

        cout << ans << endl;
    }
}

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

int main() {
	int a, b, c;
    int k;
  cin >> a >> b >> c;
  cin >> k;
  while (k && b <= a) {
  	k--;
    b *= 2;
  }
  while (k && c <= b) {
   	k--;
    c *= 2;
  }
  if (b > a && c > b) printf("Yes");
  else printf("No");
	return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define FOR1(i, n) FOR(i, 1, n+1)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));

#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl
#define dv(name, value) cerr << (name) << " is " << (value) << endl
#define da(v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl

const string YES = "Yes";
const string NO = "No";

void solve(long long H, long long N, std::vector<long long> A){
  int sum = 0;
  REP(i, N) {sum += A.at(i);}
  cout << (sum < H ? NO : YES) << endl;
}

signed main(){
  long long H;
  scanf("%lld",&H);
  long long N;
  scanf("%lld",&N);
  std::vector<long long> A(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&A[i]);
  }
  solve(H, N, std::move(A));
}


Measured memory_bytes: 1024
q,h,s,d = map(int,input().split())
n = int(input())
ans = 0
q2 = 8*q
h2 = 4*h
s2 = 2*s
b = min(q2,h2,s2,d)
if n >= 2:
    ans += b*(n//2)
    n = n-2*(n//2)
if n == 0:
    print(ans)
else:
    a = 4*q
    b = 2*q +h
    c = 2*h
    print(ans+min(a,b,c,s))


Measured memory_bytes: 38384
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    bool res = (n % 2 == 0);
    for (int i = 0; i < n / 2 && res; i++) {
        res = (s[i] == s[i + n / 2]);
    }

    cout << (res ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  ul n;
  cin >> n;
  for (ul i=0; i<n; ++i) {
    ul a;
    cin >> a;
    if (a%2==1) {
      cout << "first" << endl;
      return 0;
    }
  }
  cout << "second" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

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

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int ctoi(char c){return c-'0';}

// TODO: write
int main() {
  int n,m;cin>>n>>m;
  vector<int> a(n);rep(i,n)cin>>a[i];
  vector<pair<int,int>> cb(m);rep(i,m)cin>>cb[i].se>>cb[i].fi;
  sort(all(a));
  sort(all(cb),greater<pair<int,int>>());
  
  int cnt = 0;
  int now = 0;
  
  rep(i,n){
    if(now >= m)break;
    if(a[i] < cb[now].fi){
      a[i] = cb[now].fi;
      cb[now].se--;
      if(cb[now].se == 0)now++;
    }else break;
  }

  ll ans = SUM(a);
  print(ans);
  return 0;
}



Measured memory_bytes: 1408
text = input()

result = ''
for i in range(len(text)):
    code = ord(text[i])
    if ord('A') <= code <= ord('Z'):
        result += chr(code + 32)
    elif ord('a') <= code <= ord('z'):
        result += chr(code - 32)
    else:
        result += chr(code)

print(result)

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

typedef pair<int, int> P;

int main() {
	string s;
	while(cin >> s && s != "#"){
		P ans;
		ans.first = 0;
		ans.second = 1;
		vector<char> data;
		for(int i = 0; i < s.size(); ++i){
			if(s[i] == 'n'){
				data.push_back('N');
				i += 4;
			}
			else if(s[i] == 'w'){
				data.push_back('W');
				i += 3;
			}
		}
		reverse(data.begin(), data.end());
		for(int i = 0; i < data.size(); ++i){
			if(data[i] == 'N'){
				ans.first = max(ans.first * 2 - 90, 0);
			}
			else if(data[i] == 'W'){
				ans.first = ans.first * 2 + 90;
			}
		}
		ans.second = 1 << (data.size() - 1);
		while(ans.first % 2 == 0 && ans.first != 0 && ans.second >= 2){
			ans.first /= 2;
			ans.second /= 2;
		}
		cout << ans.first;
		if(ans.second >= 2)
			cout << "/" << ans.second;
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1212
#include <iostream>
#include <vector>
#include <cstring>

int main()
{
    int H,W,K;
    std::cin >> H >> W >> K;
    char c[H][W];
    for(int i=0; i<H; i++)
    {
        for(int j=0; j<W; j++)
        {
            std::cin >> c[i][j];
        }
    }

    // bit全探索する(2^6 * 2^6 = 4096)
    int ans = 0;
    for(int flagH = 0; flagH < (1 << H); flagH++)
    {
        for(int flagW = 0; flagW < (1 << W); flagW++)
        {
            //std::vector<std::vector<char>> c_cpy = c;
            char c_cpy[H][W];
            memcpy(c_cpy, c, sizeof(c_cpy));
            int black_num = 0;

            // 赤く塗る 
            // 選んだ行 
            for(int i=0; i<H; i++)
            {
                if(flagH & (1<<i)){
                    for(int j=0; j<W; j++)
                    {
                        c_cpy[i][j] = 'R';
                    }
                }
            }
            // 選んだ列 
            for(int j=0; j<W; j++)
            {
                if(flagW & (1<<j)){
                    for(int i=0; i<H; i++)
                    {
                        c_cpy[i][j] = 'R';
                    }
                }
            }

            // 黒の数をかぞえる 
            for(int i=0; i<H; i++)
            {
                for(int j=0; j<W; j++)
                {
                    if(c_cpy[i][j] == '#')
                    {
                        black_num++;
                    }
                }
            }
            if(black_num == K)
            {
                ans++;
            }
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 3672
n = int(input())
if n == 1:
    print(1)
else:
    times = []
    for i in range(2, n + 1, 2):
        t = 0
        while i % 2 == 0:
            i //= 2
            t += 1
        else:
            times.append(t)
    else:
        print((times.index(max(times)) + 1) * 2)

Measured memory_bytes: 9124
#include <iostream>
#include <array>
#include <map>
#include <algorithm>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
#include <random>
#include <queue>
#include <iomanip>
#include <functional>
#include <climits>
#include <tuple>
#include <unordered_map>
#include <limits>
#include <functional>
#include <cassert>
#include <numeric>
#include <bitset>
#include <set>

#define FOR(x,n) for(int x = 0; x < n; x++)
#define INPUT(x) scanf("%d",&x)
#define PUT(x) printf("%d\n",x)
#define DPUT(x) printf("%.15lf\n",x)
#define GET(x,y) std::get<x>(y)
#define CHMAX(x,y) x = std::max(x,y)
#define CHMIN(x,y) x = std::min(x,y)
#define SP_END (i != n - 1 ? ' ' : '\n') ;

using namespace std;

using ll = long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vll = std::vector<ll>;
using vpll = std::vector<pll>;
using vpii = std::vector<pii>;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vvpii = std::vector<vpii>;
using vch = std::vector<char>;
using vvch = std::vector<vch>;
using tiii = std::tuple<int, int, int>;

const ll mod197 = 1000000007LL;
const ll INF = 10000000000LL;

const double PI11 = 3.14159265359;

const int dis[5] = { 0,1,0,-1,0 };

const int disD[4] = { 0,1,1,0 };
const int disLD[3] = { 0,1,0 };

const char disC[4] = { 'U','D','R','L' };
const char disY[4] = { -1,1,0,0 };
const char disX[4] = { 0,0,1,-1 };

int main(void) {

	int n, result = 0;
	string s;
	cin >> n >> s;

	for (int i = 0; i < n; i++) {
		int flag[200] = {};
		for (int j = 0; j < n; j++) {
			if (j < i) flag[s[j]] = 1;
			else if(flag[s[j]] == 1) flag[s[j]] = 2;
		}
		CHMAX(result, (int)count(flag, flag + 200, 2));
	}

	cout << result << endl;

	return 0;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    ANS = ""
    while N > 26:
        a = N % 26
        b= N // 26
        if a == 0:
            a = 26
            b -= 1
        ANS = str(chr(96 + a)) + ANS
        N = b
    ANS = str(chr(96 + N)) + ANS
    print(ANS)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 9188
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)

#ifdef _MSC_VER
#include <intrin.h>

#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
#endif

#include <limits.h>
#include <math.h>
#include <time.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <complex>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include<atcoder/all>

using namespace std;

using namespace atcoder;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m - 1; i >= n; --i)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v, n) reverse(v, v + n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout << (x) << endl
#define pe(x) cout << (x) << " "
#define DEBUG(x) cout << #x << ": " << x << endl
#define lb(v, n) lower_bound(v.begin(), v.end(), (n))
#define ub(v, n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i, v.size()) cout << v[i] << " \n"[i==(int)v.size()-1]
template <typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template <typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7;
constexpr int MAX = 500050;
const double pi = acos(-1);
constexpr double EPS = 1e-8;
constexpr ll LINF = 1e18 + 1;
constexpr int INF = 1e9 + 1;
void Yes(bool cond) { cout << (cond ? "Yes" : "No") << '\n'; }
void YES(bool cond) { cout << (cond ? "YES" : "NO") << '\n'; }



void solve() {
	string S; cin >> S;
	ll N = S.size();
	auto sa = suffix_array(S);
	auto lcp = lcp_array(S, sa);
	ll ans = N * (N + 1) / 2 - accumulate(all(lcp), 0LL);
	print(ans);
}



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

	//int q;
	//cin >> q;
	//while (q--)
	solve();

}



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

int main(){
    int N;
    string S;
    cin >> N >> S;
    int ans = N;
    for(int i = 1;i < N;i++){
        if(S[i] == S[i-1]){
            ans--;
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll N,M;
    cin >> N >> M;
    ll X[M];
    rep(i,M) cin >> X[i];
    sort(X,X+M);
    ll out = 0;
    if(M>1){
        ll L[M-1];
        rep(i,M-1){
            L[i]= X[i+1]-X[i];
            out += L[i];
        }
        sort(L,L+M-1);
        rep(i,N-1){
            out -= L[M-2-i];
            if(i==M-2) break;
        }
    }
    cout << out << endl;
    return 0;
}


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

struct dice {
	int q1, q2, q3, q4, q5, q6;
};

int main() {
	dice d;
	char od;
	int tmp;
	(void)scanf("%d %d %d %d %d %d", &d.q1, &d.q2, &d.q3, &d.q4, &d.q5, &d.q6);
	while (scanf("%c", &od) != -1) {
		switch (od) {
		case 'N':
			tmp = d.q1;
			d.q1 = d.q2;
			d.q2 = d.q6;
			d.q6 = d.q5;
			d.q5 = tmp;
			break;
		case 'S':
			tmp = d.q6;
			d.q6 = d.q2;
			d.q2 = d.q1;
			d.q1 = d.q5;
			d.q5 = tmp;
			break;
		case 'E':
			tmp = d.q6;
			d.q6 = d.q3;
			d.q3 = d.q1;
			d.q1 = d.q4;
			d.q4 = tmp;
			break;
		case 'W':
			tmp = d.q1;
			d.q1 = d.q3;
			d.q3 = d.q6;
			d.q6 = d.q4;
			d.q4 = tmp;
			break;
		}
	}
	printf("%d\n", d.q1);
}


Measured memory_bytes: 2752
N = int(input())
# A = input().split()
A = list(map(int, input().split()))
# f = open("tmp.text")
# A = list(map(int, f.read().split()))



# left = 0
# right = N - 1
# tmp = 10**9
# while True:
#     # print(left)
#     # print(right)
#     mid = (left + right) // 2
#     # print("mid: " + str(mid))
#     lnum = A[:mid+1]
#     rnum = A[mid+1:]
#     # print(lnum)
#     # print(rnum)
#     new = abs(sum(lnum) - sum(rnum))
#     if tmp == new:
#         break
#     if tmp > new:
#         tmp = new
#     if lnum > rnum:
#         right = mid

#     # print("tmp: "+str(tmp))
#     # input()
#     if left == right:
#         break

# print(tmp)



left = A[0]
right = A[-1]

front = 1
back = 1
for _ in range(N-2):
    if left > right:
        right += A[-1 - back]
        back += 1
    else:
        left += A[front]
        front += 1

print(abs(left-right))


Measured memory_bytes: 26764
num=int(input())
word=str(input())
n_th = 0
for i in range(num):
    s1=word[:i]
    s2=word[i:]
    n=0
    for a in 'abcdefghijklmnopqrstuvwxyz':
        if (not s1.find(a) == -1) and (not s2.find(a) == -1):
            n += 1
    if n>n_th:
        n_th=n
print(n_th)

Measured memory_bytes: 3064
import Data.List
import Data.Ord
import Data.Function
import Data.Maybe
import Control.Monad

main = do
    [n,m] <- map read . words <$> getLine
    ps <- tuplify . map read . concatMap words <$> replicateM n getLine :: IO [(Int,Int)]
    cs <- tuplify . map read . concatMap words <$> replicateM m getLine :: IO [(Int,Int)]
    let solve (a,b) = (+1) . minimumIndex $ map (\(ca,cb) -> ((+) `on` abs) (ca - a) (cb - b)) cs
    mapM_ print $ map solve ps
    where
        minimumIndex xs = maybe (-1) id . flip elemIndex xs $ minimum xs

tuplify [] = []
tuplify (x:y:xs) = (x,y):tuplify xs


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
 
const int DIM = 1e5 + 5;
 
int dp[DIM];
 
int main( void ) {
    
    string str;
    cin >> str;
    
    dp[0] = 1;
    for( int i = 0; i < str.length(); i ++ ) {
        if( dp[i] == 0 )
            continue;
        
        if( str.length() - i >= 5 && str.substr( i, 5 ) == "dream" )
            dp[i + 5] = 1;
        if( str.length() - i >= 5 && str.substr( i, 5 ) == "erase" )
            dp[i + 5] = 1;
        
        if( str.length() - i >= 7 && str.substr( i, 7 ) == "dreamer" )
            dp[i + 7] = 1;
        if( str.length() - i >= 6 && str.substr( i, 6 ) == "eraser" )
            dp[i + 6] = 1;
    }
    
    if( dp[str.length()] == 1 )
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    
    return 0;
}

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

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

long long N, W, w[110], v[110];
long long DP[110][110000] = {};

int main() {
	cin >> N >> W;
	
	for(int i = 0; i < N; i++){
		cin >> w[i] >> v[i];
	}
	
	for(int i = 0; i < N; i++){
		long long w_tmp = w[i];
		long long v_tmp = v[i];
		for(int j = 0; j < W+1; j++){
			chmax(DP[i+1][j], DP[i][j]);
			if(j - w_tmp >= 0) {
				chmax(DP[i+1][j], DP[i][j - w_tmp] + v_tmp);
			}
		}
	}
	cout << DP[N][W] << endl;
}

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

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> as(n);
  for (int i = 0; i < n; i++)
  {
    cin >> as.at(i);
  }
  cout << (n - 1 + m - 2) / (m - 1) << endl;
}

Measured memory_bytes: 3748