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

int main() {
  string s;
  cin >> s;
  
  int ans = 0;
  int cur = 0;
  REP(i, s.size()) {
    char c = s.at(i);
    if (c == 'A' || c == 'C' || c == 'G' || c == 'T') {
      ++cur;
    }
    else {
      cur = 0;
    }
    ans = max(ans, cur);
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	int k;
	cin>>k;
	ll ans=0;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int l=1;l<=k;l++){
				int a[3];
				a[0]=i;a[1]=j;a[2]=l;
				sort(a,a+3);
		        int gcd1=__gcd(a[0],a[1]);
		        int gcd2=__gcd(gcd1,a[2]);
		        ans=ans+gcd2;
			
			
		}
	}
}
cout<<ans<<endl;
}

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

int main() {
	int X, N;
	cin >> X >> N;
	vector<int> P(N);
	vector<bool> B(102, true);
	for (int i = 0; i < N; i++) cin >> P[i], B[P[i]] = false;
	for (int i = 0; ; i++) {
		if (B[X - i]) {
			cout << X - i << endl;
			return 0;
		}
		if (B[X + i]) {
			cout << X + i << endl;
			return 0;
		}
	}
}

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

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


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

  vector<int> x(N), y(N);
  REP(i, N) cin >> x[i] >> y[i];

  map<pair<int, int>, int> m;
  REP(i, N) REP(j, N){
    if(i == j) continue;
    m[make_pair(x[i]-x[j], y[i]-y[j])]++;
  }

  int ans = 0;
  for(auto p : m){
    chmax(ans, p.second);
  }

  cout << N-ans << endl;

  return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int n, i, j, u, v, k;
bool is_connected[150][150];

// 最初に発見した時刻
int d[150];
// 隣接リストを調べ終えた時刻
int f[150];

void init() {
    rep(i, n + 1) rep(j, n + 1) is_connected[i][j] = false;
    rep(i, n + 1) {
        d[i] = 0;
        f[i] = 0;
    }
    d[1] = 1;
}

// must handle infinite loop
int walkDepthFirst(int src_id, int time) {
    d[src_id] = time;

    int dst_id;
    rep(dst_id, n + 1) {
        if (is_connected[src_id][dst_id]) {
            // 未訪問
            if (d[dst_id] == 0) {
                time = walkDepthFirst(dst_id, time + 1);
            }
        }
    }

    time++;
    f[src_id] = time;
    return time;
}

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

    rep(i, n) {
        cin >> u >> k;
        rep(j, k) {
            cin >> v;
            is_connected[u][v] = true;
        }
    }

    int time = 1;
    int node = 1;
    // rep(i, n) {
    //     int cur_node = i + 1;
    //     if (d[cur_node] == 0 && f[cur_node] == 0) {
    //         time = walkDepthFirst(cur_node, time);
    //         time++;
    //     }
    // }

    time = walkDepthFirst(node, time);

    rep(i, n) {
        int cur_node = i + 1;
        if (d[cur_node] == 0) {
            time = walkDepthFirst(cur_node, time + 1);
        }
    }

    rep(i, n) {
        cout << i + 1 << " " << d[i + 1] << " " << f[i + 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 3108
/*
Competitive programming template
Author: Aswin Sampath

*/


#include<bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll>vl;
typedef vector<int>vi;
typedef priority_queue<ll,vl,greater<ll>()> pq_ll_min;
typedef priority_queue<ll> pq_ll_max; 
typedef stack<ll> s;
typedef queue<ll> q;


#define pi 3.141592653589793
#define PI  acos(-1.0)
#define space " "
#define endl '\n'
#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)

#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define testcase ll t;cin>>t;while(t--)
#define dbxstl(x){for(auto ele:x)cout<<ele<<space; cout<<endl;}
#define dbxval(x){cout<<x<<endl;}

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

void solve(){
    printf("Hello\n");
}

int main(int argc, char const *argv[])
{
    ll n;
    cin>>n;
    ll dp[n],h[n];
    
    for(ll i=0;i<n;i++)cin>>h[i];
    
    memset(dp,INT_MAX,sizeof(dp));
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    

    for(ll i=2;i<n;i++){
        // dp[4] = dp[2] + (h4-h2) , dp[3] + (h4-h3)

        dp[i] = min( dp[i-2] + abs(h[i]-h[i-2]), dp[i-1] + abs(h[i]-h[i-1])  );
    }

    cout<<dp[n-1];

    cout<<endl;
    // for(ll i=0;i<n;i++){
    //     cout<<dp[i]<<space;
    // }
    // cout<<endl;
    

    return 0;
}



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

int main()
{
    double a, b, h, m, s;
    cin >> a >> b >> h >> m;
    if (((h / 6.) + (m / 360.)) > m / 30.)
    {
        s = ((h / 6.) + (m / 360.)) * M_PI - (m / 30.) * M_PI;
    }
    else
    {
        s = (m / 30.) * M_PI - ((h / 6.) + (m / 360.)) * M_PI;
    }
    double c = sqrt(a * a + b * b - 2. * a * b * cos(s));
    cout << fixed;
    cout << setprecision(10) << c << endl;
    return 0;
}

Measured memory_bytes: 4188
import bisect

a,b,c,d,e,f = map(int,input().split())

dp_w = [0] * 31
dp_w[0] = 1
for w in [a,b]:
    for i in range(w,31):
        dp_w[i] |= dp_w[i-w]

water = []
for i in range(1,31):
    if(dp_w[i]==1):
        water.append(i*100)

dp_s = [0] * 1600
dp_s[0] = 1
for w in [c,d]:
    for i in range(w,1600):
        dp_s[i] |= dp_s[i-w]

sugar = []
for i in range(1600):
    if(dp_s[i]==1):
        sugar.append(i)

ans_w =water[0]
ans_s = 0

for wi in water:
    if(f < wi):
        continue
    max_s = min(wi//100 * e, f-wi)
    ind = bisect.bisect_right(sugar,max_s)
    if(ind==0):
        continue
    si = sugar[ind-1]

    if( (ans_w + ans_s) * si > (wi+si) * ans_s):
        ans_w = wi
        ans_s = si

print('{} {}'.format(ans_w+ans_s,ans_s))

Measured memory_bytes: 65360
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
const ll mod = 1e9+7;
const int inf = INT_MAX-100;
//int dp[100000+1];
void solve(){
	int i, n, k;
	cin>>n>>k;
	int arr[n];
	vector<int> dp(n, inf);
	for(i=0;i<n;i++){
		cin>>arr[i];
	}
	dp[0]=0;
	for(i=0;i<n;i++){
		for(int j=1;j<=k;j++){
			if(i+j <n){
				dp[i+j]=min(dp[i+j], dp[i]+abs(arr[i+j]-arr[i]));
			}
		}
	}
	cout<<dp[n-1]<<endl;
}

int main()
{
	solve();
	return 0;
}

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

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		int[] v = new int[n];
		for(int i=0;i<n;i++) v[i] = in.nextInt();
		int ans = 0;
		for(int i=1;i<=k&&i<=n;i++) {
			for(int l=0;l<=i;l++) {
				List<Integer> list = new ArrayList<>();
				for(int j=0;j<l;j++) list.add(v[j]);
				for(int j=n-i+l;j<n;j++) list.add(v[j]);
				Collections.sort(list);
				int j = 0;
				for(;j<list.size();j++) {
					if(i+j==k || n+j==k || list.get(j)>0) break;
				}
				int tmp = 0;
				for(;j<list.size();j++) {
					tmp += list.get(j);
				}
				if(tmp>ans) ans = tmp;
			}
		}
		System.out.println(ans);
		in.close();
	}

}


Measured memory_bytes: 24788
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>

using namespace std;

int main(){
	double x,h;
	while(cin>>x>>h,(x||h)) printf("%lf\n",x*x + 2 * x * sqrt(h*h+x*x/4));
	
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vl vector<ll>
#define vul vector<ull>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi2d vector<vi >
#define vl2d vector<vl >
#define vpll vector<pll >

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rz resize
#define fr(i,n) for(i=0;i<(n);i++)
#define frr(i,n) for(i=(n-1);i>=0;i--)
#define fre(i,n) for(i=0;i<=(n);i++)
#define frre(i,n) for (i=(n);i>=0;i--)
#define frab(i,a,b) for(i=(a);i<(b);i++)
#define freab(i,a,b) for(i=(a);i<=(b);i++)
#define frrab(i,a,b) for(i=(b-1);i>=a;i--)
#define frreab(i,a,b) for(i=(b);i>=a;i--)

#define sz(a) int((a).size())
#define mset(a,b) (memset(a,b,sizeof(a)))
#define max3(a,b,c) (max((a),max((b),(c))))
#define min3(a,b,c) (min((c),min((a),(b))))
#define sumv(v) accumulate(all(v),ll(0))
#define productv(v) accumulate(all(v), ll(1), multiplies< ll >())
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector <ll> sprime;
vector<char> prime (1000000, true);
void sieve(ll n)
{
  //O(nloglogn) time
  sprime.pb(0);
  prime[0] = prime[1] = false;
  ll cnt = 0;
  for (ll i = 2; i <= n; ++i)
  {
    if (prime[i])
    {
      cnt++;
      sprime.pb(i);
      for (ll j = 2 * i; j <= n; j += i)
        prime[j] = false;
    }
  }
}
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll fastpowMOD(ll a, ll p, ll MOD) { if (p == 0) return 1; ll z = fastpowMOD(a, p / 2, MOD); z = (z * z) % MOD; if (p % 2) z = (z * a) % MOD; return z; }
ll fastpow(ll a, ll p) { if (p == 0) return 1; ll z = fastpow(a, p / 2); z = (z * z); if (p % 2) z = (z * a); return z; }

#define mod 1000000007
#define inf LLONG_MAX
#define minf LLONG_MIN
#define pi 3.14
#define ex 2.71

//*********************************************///
const int N = 1e5 + 5;
int i,j;
ll w[N];
ll v[N];


ll dp[105][N];
int n,wt;
ll knap(int i,int wj)
{

  if(wj==0)
    return 0;
  if(wj<0 || i<=0)
    return 1e16;

  if(dp[i][wj]!=1e15)
    return dp[i][wj];

  if(v[i]>wj)
  {
    ll x=knap(i-1,wj);
    if(x==1e15)
      x=1e16;
    return dp[i][wj]=x;
  }
  else
  {
    ll x=knap(i-1,wj);
    ll y=knap(i-1,wj-v[i])+w[i];
    x=min(x,y);
    if(x==1e15)
      x=1e16;
    return dp[i][wj]=x;
  }
}

void solve()
{
  cin>>n>>wt;
  ll sum=0;
  freab(i,1,n)
  {
    cin>>w[i]>>v[i];
    sum+=v[i];
  }
  fr(i,n+1)
    fr(j,sum+1)
      dp[i][j]=1e15;
  fr(i,n+1)
  dp[i][0]=0;
  freab(i,1,sum)
    knap(n,i);

  ll ma=-1;
  freab(i,1,sum)
    if(dp[n][i]<=wt)
      ma=i;
  cout<<ma<<endl;
}

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




Measured memory_bytes: 81152
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		double w = in.nextInt();
		double h = in.nextInt();
		double x = in.nextInt();
		double y = in.nextInt();

		double s = h * w / 2;

		int p = (x == w / 2 && y == h / 2) ? 1 : 0;

		System.out.println(s);
		System.out.println(p);
	}

}


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

using namespace std;
typedef long long ll;

int main()
{
  ll a, b;
  cin >> a >> b;
  if (b >= a)
  {
    cout << "unsafe" << endl;
  }
  else
  {
    cout << "safe" << endl;
  }
  return 0;
}


Measured memory_bytes: 3636
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;

namespace AOJ
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var nods = Sarray();
            for (var i = 1; i < N + 1; ++i)
            {
                var p = (1 < i) ? $"parent key = {nods[i / 2 - 1]}, " : string.Empty;
                var l = (i * 2 < N + 1) ? $"left key = {nods[i * 2 - 1]}, " : string.Empty;
                var r = (i * 2 + 1 < N + 1) ? $"right key = {nods[i * 2]}, " : string.Empty;
                WriteLine($"node {i}: key = {nods[i - 1]}, " + p + l + r);
            }
        }
    }
}


Measured memory_bytes: 16444
L = input()
mod = 10**9 + 7
ans_last = [2, 1]  #upper, other

for l in L[1:]:
    ans = [0, 0]
    if l == "1":
        ans[0] = ans_last[0] * 2 % mod
        ans[1] = (ans_last[0] + ans_last[1] * 3) % mod
    else:
        ans[0] = ans_last[0]
        ans[1] = (ans_last[1] * 3) % mod

    ans_last = ans
print(sum(ans_last) % mod)


Measured memory_bytes: 41708
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    s = input()
    D = Counter(s)
    res = 1
    for v in D.values():
        res = res * (v + 1) % mod
    print(res - 1)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9564
x, n = map(int, input().split())

if n != 0:
  p = list(map(int, input().split()))

  for i in range(100):
  #  print("-i:",p.count(x-i))
  #  print("+i:",p.count(x+i))
    if p.count(x-i) == 0:
      print(x-i)
      break
    elif p. count(x+i) == 0:
      print(x+i)
      break
else:
  print(x)


Measured memory_bytes: 61988
#include <iostream>
#include <algorithm>
using namespace std;
int n,c,k;
int t[100000];
int ans,now=0;
int main(){
    cin>>n>>c>>k;
    for(int i=0;i<n;i++)
        cin>>t[i];
    sort(t,t+n);
    for(int i=0;i<n;i++){
        if(t[i]>t[now]+k||i-now>=c){
            ans++;
            now=i;
        }
    }
    cout<<ans+1;
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    list<int> l;
    int q;
    cin >> q;
    auto it = l.end();
    auto it2 = it;
    int a, b;
    rep(i, q) {
        cin >> a;
        if (a == 0) {
            cin >> b;
            l.insert(it, b);
            it--;
        }
        else if (a == 1) {
            cin >> b;
            rep(i, abs(b)) {
                if (b>0)
                    it++;
                else
                    it--;
            }
        }
        else {
            l.erase(it++);
        }
    }
    for (auto o : l) {
        cout << o << endl;
    }
}


Measured memory_bytes: 18656
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def prime_factorise(n):
    a=[]
    while n%2==0:
        n//=2
        a.append(2)
    f=3
    while f*f<=n:
        if n%f==0:
            n//=f
            a.append(f)
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

n=int(input())
factors = Counter(prime_factorise(n))
ans=0
for i in factors.values():
    temp=1
    while i-temp>=0:
        i-=temp
        temp+=1
        ans+=1
print(ans)


Measured memory_bytes: 9472
#include<iostream>
using namespace std;
int main(){
    int sum=0;
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]){
            sum++;
        }
    }
    cout<<sum<<"\n";
    return(0);
}

Measured memory_bytes: 3920
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	vector<int>s,g;
	int i=0,n,m,a,b;
	for(cin>>n>>m;i<m;i++)
	{
		cin>>a>>b;
		if(a==1)s.push_back(b);
		else if(b==n)g.push_back(a);
	}
	sort(s.begin(),s.end());
	sort(g.begin(),g.end());
	int ps=0,pg=0,ls=s.size(),lg=g.size();
	for(;ps<ls&&pg<lg;)
	{
		if(s[ps]<g[pg])ps++;
		else if(s[ps]>g[pg])pg++;
		else
		{
			cout<<"POSSIBLE"<<endl;
			return 0;
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
	return 0;
}

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

int main()
{
    int a[3];
    cin >> a[0] >> a[1] >> a[2];

    // ??????????????¬???
    int mini, tmp;
    for(int i = 0; i < 3; i++) {
        mini = i;
        for(int j = i+1; j < 3; j++) {
            if(a[j] < a[mini]) mini = j;
        }
        if(mini != i) {
            tmp = a[i];
            a[i] = a[mini];
            a[mini] = tmp;
        }
    }

    // ???????????????
    cout << a[0] << " " << a[1] << " " << a[2] << endl;
    
    return 0; 
}

Measured memory_bytes: 1164
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(){
	int a[100];
	int n;

	while(scanf("%d",&n) && n != 0){
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		int swap = 0;
		for(int i=n-1;i>0;i--){
			for(int j=0;j<i;j++){
				if(a[j]>a[j+1]){
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
					swap++;
				}
			}
		}
		cout<<swap<<endl;
	}
	return 0;
}

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

#define loop(i,n) for(int i=1;i<=n;i++)
const int J=1,O=2,I=4;
int dp[1002][8];

int main() {
  int n,f;char c;
  cin>>n;
  dp[0][J]=1;
  loop(i,n){
    cin>>c;
    f=c=='J'?J:c=='O'?O:I;
    loop(p,7)loop(q,7){
      if(q&f)if(p&q)dp[i][q]+=dp[i-1][p];
      dp[i][q]%=10007;
    }
  }
  cout<<accumulate(dp[n],dp[n]+8,0)%10007<<endl;
  return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    scanf("%lld", &n);
    map<ll, ll> mp;
    while (n--) {
        ll x;
        scanf("%lld", &x);
        mp[x]++;
    }
    ll x = 0, y = 0;
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        if (!x && it->second >= 2) {
            x = it->first;
            mp[x] -= 2;
        }
        if (!y && it->second >= 2) {
            y = it->first;
            mp[y] -= 2;
            break;
        }
    }
    ll ans = x * y;
    printf("%lld\n", ans);
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;



int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  sort(ALL(s));
  int ans = 1;
  string tmp = s[0];
  for (int i = 1; i < n;i++) {
    if (s[i] == tmp) continue;
    else {
      ans++;
      tmp = s[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(10);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif
using P = pair<int,int>; using vp = vector<P>;
constexpr int MOD = /** 1000000007; //*/ 998244353;
////////////////



void solve(){
  ini(N);
  vector<ll> t(N);
  vector<double> a(N);
  rep(i , N){
    ini(T , A);
    t[i] = T;
    a[i] = 1.0 - (0.1 * A);
  }

  vector<double> rui(N + 1);
  rui[0] = 1.0;
  rep1(i , N){
    rui[i] = rui[i - 1] * a[i - 1];
  }

  ini(Q);
  rep(i , Q){
    inl(L , R);
    auto itl = upper_bound(all(t) , L);
    auto itr = upper_bound(all(t) , R);
    int l = itl - t.begin() , r = itr - t.begin();
    out( 1e9 * (rui[r] / rui[l]) ); 
  }

}


Measured memory_bytes: 5176
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

vector<vector<int>> rlt;
vector<ll> dp;
int N;

ll ff(ll n) {
	if(n<100)cout << "n=" << n << endl;
	if (dp[n] != 0) return dp[n];
	if (n == 0)return dp[n] = 1;
	int num = 0;
	for (int i = 0; i < N; i++) {
		if (n & (1 << i))num++;
	}

	int temp;
	for (int i = 0; i < N; i++) {
		if ((1 << i) & n) {
			if (rlt[num-1][i]) {
				temp = n ^ (1 << i);
				dp[n] += ff(temp);
				dp[n] %= DIV;
			}
		}
	}

	return dp[n]%=DIV;
}


int main() {
	cin >> N;
	rlt = vector<vector<int>>(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> rlt[i][j];
		}
	}

	ll mx = 1 << N;
	dp = vector<ll>(mx);
	dp[0] = 1;
	for (ll i = 0; i < mx - 1; i++) {
		int num = 0;
		for (ll k = 0; k < N; k++) {
			if (i & (1 << k))num++;
		}

		for (ll j = 0; j < N; j++) {
			if ((!(i & (1 << j))) && rlt[num][j]) {
				dp[i ^ (1 << j)] += dp[i];
				dp[i ^ (1 << j)] %= DIV;
			}
		}

	}

	cout << dp[mx - 1] << endl;
}



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

using namespace std;

long long inf=1000000007;

int main(){
	long long n,x;
	cin>>n>>x;

	while(n!=0 || x!=0){
		long long cnt=0;
		for(long long i=1;i<=n;i++){
			for(long long j=i+1;j<=n;j++){
				if(x-i-j>j && x-i-j<=n) cnt++;
			}
		}
		cout<<cnt<<endl;
		cin>>n>>x;
	}

	return 0;
}



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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}
 
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

int main() {
	int N; cin >> N;
	vector<pii> pts(N);

	rep(i, N) {
		int a, b; cin >> a >> b;
		pts[i] = mp(a, b); 
	}

	sort(ALL(pts));

	map<pii, int> T;

	rep(i, N) {
		rep(j, i) {
			++T[mp(pts[i].fi - pts[j].fi, pts[i].se - pts[j].se)];
		}
	}

	int ans = N;

	for (const auto& p : T) {
		ans = min(ans, N - p.se);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto S = RD!string;
	long ans;
	foreach (i; 1..N-1)
	{
		auto cnt1 = new bool[](26);
		foreach (j; 0..i)
		{
			cnt1[S[j]-'a'] = true;
		}
		auto cnt2 = new bool[](26);
		foreach (j; i..N)
		{
			cnt2[S[j]-'a'] = true;
		}

		long cnt;
		foreach (j; 0..26)
		{
			if (cnt1[j] && cnt2[j])
				++cnt;
		}
		ans = max(ans, cnt);
	}

	writeln(ans);
	stdout.flush();
	debug readln();
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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;}

const ll INF=1e18;


int main()
{
    string s;
    cin >> s;
    ll n=s.length();
    bool ok=true;
    rep(i,n){
        if(i%2==0 && s[i]=='L'){
            ok=false;
            break;
        }
        if(i%2==1 && s[i]=='R'){
            ok=false;
            break;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))

#define y0 y12345
#define y1 y54321
typedef unsigned long ul;
typedef long long ll;
//typedef pair<int, int> mpair;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
using namespace std;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
   	int n,k;cin>>n>>k;
	double ans = 0;
	for(int i = 1;i <= n;i++){
		double a = (int)ceil((double)k/i);
		//cout << a << endl;
		rep(j, 20){
			if(a<=1){
				ans += (double)pow(2.0, -1*j);
				//cout << j << endl;
				break;
			}
			a/=2;
		}

	}
	printf("%.12f\n",ans / (double)n);
	return 0;
}


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

int main(){
    int64_t N, M;
    cin >> N >> M;

    if(N >= M / 2){
        cout << M / 2 << endl;
    }
    else {
        int64_t t = M - N * 2;
        cout << N + t / 4 << endl;
    }

    return 0;
};

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
 
    pair<int, int> even_nodes(n, 1);
    pair<int, int> odd_nodes(n / 2 + 2, n / 2);

    for (int i = 0; i < m; ++i){
        if (i % 2 == 0) {
            cout << even_nodes.first-- << " " << even_nodes.second++ << endl;
        } else {
            cout << odd_nodes.first++ << " " << odd_nodes.second-- << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3588
import sys
input_lines1 = sys.stdin.readlines()
for line in input_lines1:
    strBuf = line.replace('\n', '').split(' ')
    maxValue = 0
    index = 0
    start = -1
    end = 0
    for idx in range(len(strBuf[0])) :
        if start == -1 :
            if strBuf[0][idx:idx+1] == 'A' :
                start = idx
            else:
                continue

        if strBuf[0][idx:idx+1] == 'Z' :
            if not 'Z' in strBuf[0][idx+1:] :
                end = idx
                break
print end - start + 1


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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;i++)
#define FOR(i,a,b) for(ll i=(a),i##_cond=(b);i<i##_cond;i++)
#define ROF(i,a,b) for(ll i=(a)-1,i##_cond=(b);i>=i##_cond;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;

const ll inf = 1ll<<62;
const ll mod = 1e9+7;

#define int ll

int h,w;
vs s;
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

bool search(int x, int y){
  bool f = false;
  
  rep(i,sz(dx)){
    int nx = x + dx[i], ny = y + dy[i];
    if(0 <= nx and nx < h and 0 <= ny and ny < w and s[nx][ny] == '#'){
      s[nx][ny] = '.';
      f = true;
      search(nx, ny);
    }
  }

  return f;
}


main()
{
  cin >> h >> w;
  s.resize(h);
  rep(i,h) cin >> s[i];

  rep(i,h) rep(j,w){
    if(s[i][j] == '#'){
      s[i][j] = '.';
      if(search(i,j) == false){
	cout << "No\n";
	return 0;
      }
    }
  }
  dump(s);
  cout << "Yes\n";
}

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

using namespace std;
typedef long long ll;
const int MAXN = 100100;

int N, M;
string S, T;
int ps[MAXN], ps2[MAXN];

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> S >> T;
    N = S.length();
    M = T.length();

    for (int i = 0; i < N; i++)
        ps[i+1] = ps[i] + (S[i] - 'A' + 1);
    for (int i = 0; i < M; i++)
        ps2[i+1] = ps2[i] + (T[i] - 'A' + 1);

    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if ((ps[b] - ps[a-1]) % 3 == (ps2[d] - ps2[c-1]) % 3)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Measured memory_bytes: 1744
#include<bits/stdc++.h>
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
#define PI 3.141592653589793
int main()
{
  double A,B,H,M;
  cin>>A>>B>>H>>M;
  double  kauddo=abs((H*5+M/12)-M);
  if(kauddo>30){
    kauddo=60-kauddo;
  }
  kauddo*=6;
  //cout<<kauddo<<"\n";
  double radian = kauddo * PI / 180.0;
  double  ans=(A*A)+(B*B)-(2*A*B*cos(radian));
  //cout<<cos(radian)<<"\n";
  ans=sqrt(ans);
  printf("%.10lf\n", ans);
  return 0;
}


Measured memory_bytes: 4220
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int a, b, c; cin >> a >> b >> c;
    set<int> st;
    int mul = 1;
    while (true) {
        int mod = (a * mul) % b;
        if (mod == c) {
            cout << "YES" << endl;
            return 0;
        } else if (st.find(mod) != st.end()) {
            cout << "NO" << endl;
            return 0;
        }
        st.insert(mod);
        mul++;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>

using namespace std;

int main(){
  int a,b,c,i,j,k,l,n,cnt=0;
  vector <int> v;
  
  cin>>a>>b>>c>>n;
  for(i=0;i<=a;i++){
    for(j=0;j<=b;j++){
      for(k=0;k<=c;k++){
        l=i*500+j*100+k*50;
        v.push_back(l);
      }
    }
  }
  
  for(i=0;i<v.size();i++){
    if(v[i]==n)
      cnt++;
  }
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    pair<ll,ll> A[100007];
    int N,H,AM=0,C=0;cin >> N >> H;
    rep(i,N){
        cin >> A[i].first >> A[i].second;
        if(A[i].first>AM){
            AM=A[i].first;
        }
    }
    psortsecond(A,N);
    reverse(A,A+N);
    ll i=0;
    while(A[i].second>AM){
        H-=A[i].second;
        C++;
        i++;
        if(H<=0){
            break;
        }
    }
    ll K=0;
    if(H>0){
        K=(H-1)/AM+1;
    }
    cout << K+C << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 10000000000000000; //10^16
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;


int main(void){
    string N;
    cin >> N;
    int L = N.size();
    vector<int> d(3, 0),l(3, 0);
    int K;
    cin >> K;
    int cnt = 0;
    for(int i = 0; i < L; i++){
        if(N.at(i) != '0'){
            d.at(cnt) = (int)(N.at(i) - '0');
            l.at(cnt) = L - i;
            cnt++;
        }
        if(cnt == 3){
            break;
        }
    }
    ll ans = 0;
    ll tmp;
    int D,d1,d2,l1,l2; D = d.at(0); d1 = d.at(1); d2 = d.at(2); l1 = l.at(1); l2 = l.at(2);
    if(K == 3){
        for(int i = 3; i <= L - 1; i++){
            ans += 9*9*9 * (i-1) * (i-2) /2; 
        }
        ans += 9*9 * (L-1) * (L-2) * (D-1)/2;
        if(d1 != 0){
            ans += (l1 - 1) * 9 * (d1 - 1);
            ans += 9*9* (l1 - 1) * (l1 - 2) / 2;
        }
        if(d2 != 0){
            ans += d2-1;
            ans += (l2-1)*9;
            ans += 1;
        }
    }
    else if(K == 2){
        for(int i = 2; i <= L - 1; i++){
            ans += 9*9 * (i-1); 
        }        
        ans += (L-1)* 9 * (D-1);
        if(d1 != 0){
            ans += d1-1;
            ans += (l1-1)*9;
            ans += 1;
        }
    }
    else{
        for(int i = 1; i <= L - 1; i++){
            ans += 9; 
        }    
        ans += D;
    }
    printf("%lld\n", ans);
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define r0 return 0;
#define f(k,i,n,j) for(ll k=i;k<=n;k=k+j)
#define cin(a) cin>>a;
#define loop while(t--)
#define vi vector<int>
#define vii vector<long long int>
#define SORT(v) sort(v.begin(),v.end());
#define mod (1e9+7)
#define crap ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
signed main()
{
    crap;
    string s,t;
    cin>>s>>t;
    int a,b;
    cin>>a>>b;
    string k;
    cin>>k;
    if(k==s)
    a--;
    else if(k==t)
    b--;
    cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
#include <numeric>
#include <iomanip>

using namespace std;

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

    cout << b * (t / a) << endl;
}

/*

long int gcd(long int a, long int b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    
    return b ? gcd(b, a % b) : a;
}

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

*/

Measured memory_bytes: 256
def calc(t, s)
  tones = %w(C C# D D# E F F# G G# A A# B)
  [1, 2].each{|j|
    i = t.size - j
    s.reverse.each{|e|
      idx = tones.index(e)
      if tones.index(t[i]) == idx
        i -= 1
      elsif (tones.index(t[i]) - 1) % 12 == idx && i < t.size - 1
        i += 1
      elsif (tones.index(t[i]) + 1) % 12 == idx && i > 0
        i -= 2
      else
        break
      end
      return 'Yes' if i == -1
    }
  }
  'No'
end
gets.to_i.times do
  gets
  t = gets.chomp.split
  s = gets.chomp.split
  puts calc(t, s)
end

Measured memory_bytes: 18528
n=int(input())
ss=input()

# Z-algorithm
# 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
#s='aaabaaaab'
def func(s):
  a=[0]*len(s)
  a[0]=len(s)
  i,j=1,0
  while i<len(s):
    while i+j<len(s) and s[j]==s[i+j]:
      j+=1
    a[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<len(s) and k+a[k]<j:
      a[i+k]=a[k]
      k+=1
    i+=k
    j-=k
  return a
ans=0
for i in range(n):
  a=func(ss[i:])
  for j in range(len(a)):
    ans=max(ans,min(a[j],j))
print(ans)


Measured memory_bytes: 79324
#include<stdio.h>
int a, b, c;
int main(){
  scanf("%d%d%d", &a, &b, &c);
  if(a==b && a==c){
    printf("1\n");
  }else if(a==b || b==c || c==a){
    printf("2\n");
  }else{
    printf("3\n");
  }
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define UINF 18446744073709551615
#define F first
#define S second
#define ll long long
#define N 110
using namespace std;
ll n,m,s,dp[55][N*N],c[55],d[55],sum=0;
vector<pair<ll,pair<ll,ll> > > vt[55];
priority_queue<pair<ll,pair<ll,ll> > > pq;
int main(){
	ll i,j,x,y,a,b;
	scanf("%lld%lld%lld",&n,&m,&s);
	for(i=0;i<m;i++)
	{
		scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		sum+=a;
		x--;
		y--;
		vt[x].push_back(make_pair(y,make_pair(a,b)));
		vt[y].push_back(make_pair(x,make_pair(a,b)));
	}
	for(i=0;i<n;i++)
	{
		scanf("%lld%lld",&c[i],&d[i]);
	}
	memset(dp,127,sizeof(dp));
	dp[0][min(s,sum)]=0;
	pq.push(make_pair(0,make_pair((ll)0,min(s,sum))));
	while(!pq.empty())
	{
		x=pq.top().S.F;
		a=-pq.top().F;
		b=pq.top().S.S;
		pq.pop();
		if(dp[x][b]<a)
		{
			continue;
		}
		for(i=0;i<vt[x].size();i++)//走到另外一个地方
		{
			if(b<vt[x][i].S.F)
			{
				continue;
			}
			y=vt[x][i].F;
			if(dp[y][b-vt[x][i].S.F]>a+vt[x][i].S.S)
			{
				dp[y][b-vt[x][i].S.F]=a+vt[x][i].S.S;
				pq.push(make_pair(-dp[y][b-vt[x][i].S.F],make_pair(y,b-vt[x][i].S.F)));
			}
		}
		for(i=b+c[x];i<=sum;i+=c[x])//兑换银币
		{
			if(dp[x][i]>a+(i-b)/c[x]*d[x])
			{
				dp[x][i]=a+(i-b)/c[x]*d[x];
				pq.push(make_pair(-dp[x][i],make_pair(x,i)));
			}
		}
	}
	for(i=1;i<n;i++)
	{
		a=LINF;
		for(j=0;j<=sum;j++)
		{
			a=min(a,dp[i][j]);
		}
		printf("%lld\n",a);
	}
	return 0;
}

Measured memory_bytes: 57624
fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    
    val A = readInputLine().split(" ").map { it.toInt() }
    
    // (出席番号, 登校順)
    val AIndexed = mutableListOf<Pair<Int, Int>>()
    
    for ((i, a) in A.withIndex()) {
        AIndexed.add(Pair(a, i + 1))
    }

    println(AIndexed.sortedBy { it.first }.unzip().second.joinToString(" "))
}

fun readInputLine(): String {
    return readLine()!!
}


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

int main() {
    long long n, a, m = 1000000001, ans = 0, cnt = 0;
    cin >> n;
    for (long long i = 0; i < n; i++) {
        cin >> a;
        if (a < 0) {
            ++cnt;
            a = -a;
        }
        ans += a;
        m = min(m, a);
    }
	cout << ans - (cnt % 2 == 1 ? m * 2 : 0) << endl;
    return 0;
}

Measured memory_bytes: 256
n, a, b, c, d = gets.split.map(&:to_i)
s = gets.chomp
s = " " + s
flag = true
sa = s.slice(a, c-a+1)
flag = false if sa.include?("##")
sb = s.slice(b, d-b+1)
flag = false if sb.include?("##")
if c > d
  s_over = s.slice(b-1, (d+1)-(b-1)+1)
  flag = false if !s_over.include?("...")
end
puts flag ? "Yes" : "No"


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

int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> a(M);
  for (auto & A : a)
    cin >> A;
  vector<int> path(N + 1);
  path[0] = 1;
  int idx = 0;
  int mod = 1000000007;
  for (int i = 1; i <= N; ++i)
  {
    if ((idx < M) && (a[idx] == i))
    {
      path[i] = 0;
      ++idx;
      continue;
    }
    int sum = 0;
    if (0 <= i - 1)
      sum += path[i - 1];
    if (0 <= i - 2)
      sum += path[i - 2];
    path[i] = sum%mod;
  }
  cout << path[N];
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
    ll n;
    cin>>n;
    vector<ll> v(n,0);
    bool f=true;

    rep(i,n){
        cin>>v[i];
        if(v[i]==0){f=false;}
    }


    if(!f){
        cout<<0<<endl;
        return 0;
    }

    ll sum = v[0];

    ll m = 1000000000000000000;
    if(v[0]>m){
        cout<<-1<<endl;
        return 0;
    }

    for(int i=1;i<n;i++){
        ll psum = sum;
        sum*=v[i];

     if(sum>m||sum<0){
         cout<<-1<<endl;
         return 0;
     }else if(sum/v[i]!=psum||sum<psum){
         cout<<-1<<endl;
         return 0;
     }

    }

    cout<<sum<<endl;



return 0;
}


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

int main() {
    int a[3];
    int r,g,b,n;
    cin >> a[0] >> a[1] >> a[2] >> n;
    sort(a, a+ 3);
    int result = 0;
    int dp[n + 1];
    for(int i = 0;i <= n;i++) dp[i] = 0;
    dp[0] = 1;
    for(int i = a[0];i <= n;i++){
        dp[i] += dp[i - a[0]];
    }
    for(int i = a[1];i <= n;i++){
        dp[i] += dp[i - a[1]];
    }
    for(int i = a[2];i <= n;i++){
        dp[i] += dp[i - a[2]];
    }
    cout << dp[n] << endl;
    
}

Measured memory_bytes: 256
from collections import *
import sys
inp = raw_input

def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]


N, M = nl()
A = nl()

from heapq import *

pq = []
for a in A:
    heappush(pq, -a)

for _ in range(M):
    v = heappop(pq)
    a = -v
    heappush(pq, -(a//2))

tot = 0
for _ in range(N):
    v = heappop(pq)
    tot += -v
print(tot)


Measured memory_bytes: 12972
def tax(A,B):
    for i in range(1, 800001):
        t1=int(i*0.08)
        t2=int(i*0.1)
        if t1 == A:
            if t2 == B:
                return i
        

if __name__ == "__main__":
    A, B = input().split()
    A = int(A)
    B = int(B)
    i=tax(A,B)
    if i == None:
        print("-1")
    else:
        print(i)

Measured memory_bytes: 3064
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())

G = [[] for _ in range(N + 1)]
m = map(int, read().split())
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

par = [0] * (N + 1)
visited = [0] * (N + 1)
root = 1
visited[root] = 1
q = deque([root])
while q:
    v = q.popleft()
    for w in G[v]:
        if visited[w]:
            continue
        visited[w] = 1
        par[w] = v
        q.append(w)

print('Yes')
print(*par[2:], sep='\n')


Measured memory_bytes: 118400
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

int main(){
  	ll n,cnt=0;
  	cin>>n;
  	ll arr[n+1];
  	for(ll i=1;i<=n;i++) cin>>arr[i];
  	map<ll,ll> mp;
  	for(ll i=n;i>=1;i--){
      cnt+=mp[arr[i]+i];
      mp[i-arr[i]]++;
    }
  	cout<<cnt;
      
    return(0);
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n;
  cin >> n;
  string in[120];
  pair<pair<string,int>,int> p[110];
  for(int i=0; i<n; ++i){
    int t;
    cin >> in[i] >> t;
    p[i] = make_pair(make_pair(in[i],-t),i);
  }
  sort(p,p+n);
  for(int i=0; i<n; i++) cout << p[i].second+1 << endl;

}

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

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

    int res = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        if (s[l] == s[r]) {
            l++; r--;
            continue;
        }

        if (s[l] == 'x') {
            l++;
            res++;
        }
        else if (s[r] == 'x') {
            r--;
            res++;
        }
        else {
            puts("-1");
            return 0;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 512
n = int(input())
s = [input() for _ in range(n)]
ans = ""
abc = "abcdefghijklmnopqrstuvwxyz"
for i in range(26):
    cnt = s[0].count(abc[i])
    for j in range(1, n):
        if cnt >= s[j].count(abc[i]):
            cnt = s[j].count(abc[i])
    if cnt != 0:
        ans += abc[i]*cnt
print(ans)

Measured memory_bytes: 9092