akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
    int N, Q, cnt;
	string S;
	cin >> N >> Q >> S;
    int res = 0;
    int pos[N] = {};
    cnt = 0;
    for (int i = 0; i < N; i++) {
        pos[i] = cnt;
        if (S[i] == 'A' && i+1 < N) {
            if (S[i+1] == 'C') {
                cnt++;
                pos[i+1] = cnt;
                i++;
            }
        } 
    }
    for (int i = 0; i < Q; i++) {
        res = 0;
        int li, ri;
        cin >> li >> ri;
        
        cout << pos[ri-1] - pos[li-1] << endl;
    }
        
	return 0;
}

Measured memory_bytes: 1408
#include <cmath>
#include <chrono>
#include <cstdio>
#include <iostream>
using namespace std;

unsigned int xor128() {
    static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
    unsigned int t;
    t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
}

inline bool rand_bool(double prob) {
    constexpr double x = 1LL<<32; // uint_max+1
    return xor128() < prob * x;
}

int timelimit = 2 * 1000, elapsed = 0, margin = 50;

class Timer {
  chrono::system_clock::time_point start_time = chrono::system_clock::now();
public:
  Timer() {}
  int get_elapsed_time() {
    auto diff = chrono::system_clock::now() - start_time;
    return chrono::duration_cast<chrono::milliseconds>(diff).count();
  }
} timer;


const int D = 365;
int c[26], s[D][26];

long long calc_score(int *ans, int d0) {
    long long score = 0;
    int last[26] = {};
    fill(last, last+26, -1);
    for (int d = 0; d < d0; d++) {
        score += s[d][ans[d]];
        last[ans[d]] = d;
        for (int i = 0; i < 26; i++)
            score -= c[i] * (d - last[i]);
    }
    return score;
}

int main() {
    scanf("%*d");
    for (int i = 0; i < 26; i++) cin >> c[i];
    for (int d = 0; d < D; d++)
        for (int i = 0; i < 26; i++) cin >> s[d][i];

    int ans[D];
    for (int d = 0; d < D; d++) {
        long long best_score = -(1LL<<60);
        int best_type = -1;
        for (int i = 0; i < 26; i++) {
            ans[d] = i;
            long long score = calc_score(ans, d+1);
            if (best_score < score) {
                best_score = score;
                best_type = i;
            }
        }
        ans[d] = best_type;
    }

    int iter = 0;
    long long best_score = calc_score(ans, D);
    int best_ans[D];
    copy(ans, ans+D, best_ans);
    while (timer.get_elapsed_time() + margin < timelimit) {
        int d = xor128()%D;
        int i = iter%26;
        int save = ans[d];
        ans[d] = i;
        long long score = calc_score(ans, D);
        bool update = best_score <= score;
        if (!update) {
            const double r = 1 - double(timer.get_elapsed_time()) / timelimit,
                temp = r * 500,
                prob = exp((score - best_score) / temp);
            update = rand_bool(prob);
        }
        if (best_score < score) {
            cerr << iter << ' ' << best_score << " " << score <<endl;
            best_score = score;
            copy(ans, ans+D, best_ans);
        }
        if (update) {
            // 
        } else {
            ans[d] = save;
        }
        iter++;
    }

    for (int d = 0; d < D; d++) cout << ans[d] + 1 << endl;
}


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

namespace ABC152
{
    class C
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] P = Console.ReadLine().Split().Select(int.Parse).ToArray();

            int min = int.MaxValue;
            int res = 0;
            for (int i = 0; i < N; i++)
            {
                if (P[i] <= min) { res++; }
                min = Math.Min(min, P[i]);
            }

            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 35676
n = int(input())
p = [[0,0,0]]
for i in range(n):
    p.append([int(k) for k in input().split()])
res = 'No'

for i in range(1, n+1):
    t = p[i][0] - p[i-1][0]
    d = p[i][1] - p[i-1][1] + p[i][2] - p[i-1][2]
    if t % 2 == d % 2 and t >= d:
        continue
    break
else:
    res = 'Yes'

print(res)


Measured memory_bytes: 21156
#include<iostream>

using namespace std;


int main(){

	int H,W;
	while(true)
	{
		cin >> H >> W;

		if(H+W == 0) break;

		for(int i=0;i<H;i++)
		{
			for(int k=0;k<W;k++)
			{
				if((i == 0)||(i == H-1)||(k == 0)||(k ==W-1)) cout << "#";
				else cout << ".";
			}
			cout << "\n";
		}
		cout << "\n";

	}
	return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

int constexpr N = 200009;
int n;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<pair<int, int>> v(n);
    for(auto& x : v) cin >> x.se >> x.fi;
    sort(begin(v), end(v));

    int t = 0;
    for(auto& x : v) {
        if(t + x.se > x.fi) return cout << "No" << endl, 0;
        t += x.se;
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x;
  cin>>x;
  for(int i=1;i<=x;i++)
  {
    if((i*360)%x==0)
    {
      cout<<(i*360)/x<<"\n";
      break;
    }
  }
  return 0;
}

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

#define inf 0x3f3f3f3f
#define INF 1000111000111000111LL
#define mod 1000000007
#define pi acos(-1.0)
#define eps 1e-8
#define endl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define all(cc) (cc).begin(),(cc).end()
using lli = long long int ;
using pii = pair<int, int> ;
using vi = vector<int> ;
using vb = vector<bool> ;
using vvi = vector<vector<int>> ;
using vlli = vector<long long int> ;
using vpii = vector<pair<int, int>> ;

int main()
  {
    ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
    int h, w, x, y, dp[1005][1005] ;
    char grid[1005][1005] ;
    dp[1][1]=1 ;
    cin>> h >> w ;
    for(int i=1 ; i<=h ; i++)
      for(int j=1 ; j<=w ; j++)
        cin>> grid[i][j] ;
    for(int i=2 ; i<=h+w-1 ; i++)
      for(int j=0 ; j<min({i, (w-max(0, i-h)), h}) ; j++)
        {
          tie(x, y)=mp(min(h, i)-j, max(0, i-h)+j+1) ;
          if(grid[x][y]=='.') dp[x][y]=(dp[x-1][y]+dp[x][y-1])%mod ;
        }
    cout<< dp[h][w] ;
  }


Measured memory_bytes: 5120
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#define P pair<long long, long long>

using namespace std;
const long long int MOD=1e9+7;


int main(){
  long long n, m;
  vector<P> v[100009];
  priority_queue<P, vector<P>, greater<P>> Q1, Q2;
  cin >>n >> m;
  for(int i=0;i<m;i++){
    long long s, t, c;
    cin >> s >> t >> c;
    s--;t--;
    v[s].push_back(P(c, t));
  }
  for(int j=0;j<v[0].size();j++){
    Q1.push(v[0][j]);
    Q2.push(v[0][j]);
  }
  for(int i=1;i<n;i++){
    while(!Q1.empty() && Q1.top().second<i)Q1.pop();
    while(!Q2.empty() && Q2.top().second<i)Q2.pop();
    if(Q1.empty()){
      cout << -1 << endl;
      return 0;
    }
    long long tp = Q1.top().first;
    Q1.push(P(tp+Q2.top().first, Q2.top().second));
    for(int j=0;j<v[i].size();j++){
      Q1.push(P(tp + v[i][j].first, v[i][j].second));
      Q2.push(P(v[i][j]));
    }
  }
  cout << Q1.top().first << endl;
}


Measured memory_bytes: 12688
import sys
def main():
    for line in sys.stdin:
        n = int(line)
        if n != 0:
            a = []
            for _ in range(n):
                a.append(list(map(int, input().split())))
            a.append(list(range(n + 1)))

            for x in range(n):
                hoge = 0
                for y in range(n):
                    hoge += a[y][x]
                else:
                    a[n][x] = hoge

            for x in range(n + 1):
                hoge = 0
                for y in range(n):
                    hoge += a[x][y]
                else:
                    if x != n:
                        a[x].append(hoge)
                    else:
                        a[n][n] = hoge

            for x in range(n + 1):
                for y in range(n + 1):
                    print("{0:5d}".format(a[x][y]), end = "")
                else:
                    print()

        else:
            break


if __name__ == "__main__":
    main()

Measured memory_bytes: 7820
N=int(input())
S=input()
counter=[[0 for i in range(N)] for _ in range(3)]#i+1より右側にあるR(0),G(1),B(2)の数
if S[N-1]=="R":
  counter[0][N-1]=1
elif S[N-1]=="G":
  counter[1][N-1]=1
else:
  counter[2][N-1]=1
for i in range(1,N):
  if S[N-1-i]=="R":
    counter[0][N-1-i]=counter[0][N-i]+1
  elif S[N-1-i]=="G":
    counter[1][N-1-i]=counter[1][N-i]+1
  else:
    counter[2][N-1-i]=counter[2][N-i]+1
  counter[0][N-1-i]=max(counter[0][N-i],counter[0][N-1-i])
  counter[1][N-1-i]=max(counter[1][N-i],counter[1][N-1-i])
  counter[2][N-1-i]=max(counter[2][N-i],counter[2][N-1-i])
ans=0
for i in range(N-1):
  if S[i]=="R":
    for j in range(i+1,N):
      if S[j]=="G":
        ans+=counter[2][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="B":
            ans-=1
      elif S[j]=="B":
        ans+=counter[1][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="G":
            ans-=1
for i in range(N-1):
  if S[i]=="G":
    for j in range(i+1,N):
      if S[j]=="R":
        ans+=counter[2][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="B":
            ans-=1
      elif S[j]=="B":
        ans+=counter[0][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="R":
            ans-=1
for i in range(N-1):
  if S[i]=="B":
    for j in range(i+1,N):
      if S[j]=="R":
        ans+=counter[1][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="G":
            ans-=1
      elif S[j]=="G":
        ans+=counter[0][j]
        if 2*j-i<=N-1:
          if S[2*j-i]=="R":
            ans-=1
print(ans)

Measured memory_bytes: 69236
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int N;
  cin >>N;
  vector<P> jobs(N);
  rep(i,N) cin >> jobs[i].second >> jobs[i].first;
  sort(jobs);
  ll t = 0;
  rep(i,N){
    t += jobs[i].second;
    if(t > jobs[i].first){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#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 srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    bitset<4000001> bt;
    bt.set(0);
    int sm = 0;
    rep(i,n){
        int a;
        cin >> a;
        sm += a;
        bt |= bt << a;
    }
    for(int i = (sm+1)/2; i <= sm; i++){
        if(bt.test(i)){
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}


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

template<typename T>
vector<T> convert_base(T x, T b) {
  vector<T> ret;
  T t = 1, k = abs(b);
  while (x) {
    ret.emplace_back((x * t) % k);
    if (ret.back() < 0) ret.back() += k;
    x -= ret.back() * t;
    x /= k;
    t *= b / k;
  }
  if (ret.empty()) ret.emplace_back(0);
  reverse(begin(ret), end(ret));
  return ret;
}

int main() {
  int N, K;
  cin >> N >> K;
  auto ret = convert_base(N, K);
  cout << ret.size() << "\n";
}

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

#define print(x) for(auto it : x) cout<< it << " "; cout << endl;
#define PI 3.14159265
typedef long long ll;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n, k; cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for (int i = 0; i < k; ++i) {
        ans += v[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX=200000;

int main(){
    int R[MAX], n;
    cin >> n;
    for (int i=0; i<n; i++) cin >> R[i];

    int maxv = -2000000000;
    int minv = R[0];

    for (int i=1;i<n;i++){
        maxv = max(maxv, R[i]-minv);
        minv  =min(minv, R[i]);
    }
    cout << maxv << endl;

    return 0;
}



Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k, q; cin >> n >> k >> q;
  vector<ll> A(n); rep(i, n) cin >> A[i];
  ll mn = longinf;
  rep(i, n) {
    ll tmp = A[i];
    priority_queue<ll, vector<ll>, greater<ll>> que;
    vector<ll> v;
    rep(j, n) {
      if(A[j] < tmp) {
        while((int)que.size() >= k) {
          v.push_back(que.top()); que.pop();
        }
        while(!que.empty()) que.pop();
      } else {
        que.push(A[j]);
      }
    }
    while((int)que.size() >= k) {
      v.push_back(que.top()); que.pop();
    }
    sort(all(v));
    if((int)v.size() < q) continue;
    mn = min(v[q-1]-v[0], mn);
  }
  cout << mn << "\n";
  return 0;
}


Measured memory_bytes: 3704
ans = "WA"
s = list(input())
if s[0] == "A":
    c_index = [i for i, x in enumerate(s[2:-1]) if x == 'C']
    if len(c_index) == 1:
        s.pop(c_index[0] + 2)
        s.pop(0)
        s = "".join(s)
        if s.islower():
            ans = "AC"
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
int gcd(int a,int b){
	if (a%b == 0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}

}

//最小公倍数
int lcm(int a,int b){
	return a /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}



  








      

 
int main(){
    int n;
    cin >> n;
    if (n%1000)cout << 1000-n%1000<< endl;
    else cout << 0 << endl;
}


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

long long N, M;
vector<vector<int>> G;
vector<int> color;
bool flag;

void dfs(int s, int c){
    if(flag) return;

    for(int t : G[s]){
        if(color[t] != -1){
            if(color[t] != c){
                flag = true;
                return;
            }else continue;
        }
        if(color[t] == -1){
            color[t] = c;
            dfs(t, 1-c);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    G.resize(N);
    for(int i=0; i<M; i++){
        int A, B;
        cin >> A >> B;
        A--; B--;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    color.resize(N, -1);
    flag = false;
    dfs(0, 0);

    if(flag){
        cout << N*(N-1)/2 - M << endl;
        return 0;
    }
    int cnt0 = 0, cnt1 = 0;
    for(int i=0; i<N; i++){
        if(color[i] == 0) cnt0++;
        else cnt1++;
    }

    long long ans = 0;
    for(int i=0; i<N; i++){
        int tmp;
        if(color[i] == 0) tmp = cnt1;
        else tmp = cnt0;
        ans += tmp - G[i].size();
    }
    cout << ans / 2 << endl;

    return 0;
}


Measured memory_bytes: 6528
A = int(input())
B = int(input())
C = int(input())
X = int(input())
cnt = 0

for i in range(A + 1):
  for j in range(B + 1):
    y = X - i * 500 - j * 100
    if y % 50 == 0 and 0 <= y <=50*C:
        cnt += 1
        
print(cnt)

Measured memory_bytes: 3060
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
using ld=long double;
//#define int long long
//#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279;
int fact(int i) {
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int keta(int n) {
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
int ketasum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
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;
}
string s;
int main(void) {
    cin >> s;
    s[3] = '8';
    cout << s << endl;
    return 0;
}

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

#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

int main() {

    long long int n, m;
    cin >> n >> m;

    vector< vector< long long int > > v( n, vector< long long int >() );

    for ( long long int i = 0; i < m; i++ ) {
        long long int a, b;
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back( b );
        v[b].push_back( a );
    }

    queue< long long int > q;
    q.push( 0 );

    long long int f[114514] = {};
    for ( long long int i = 0; i < n; i++ ) {
        f[i] = -1;
    }
    long long int cnt = 0;

    while( !q.empty() ) {
        long long int k = q.front();
        q.pop();
        for ( long long int i = 0; i < v[k].size(); i++ ) {
            long long int next = v[k][i];
            if ( f[next] >= 0 ) continue;
            f[next] = k;
            cnt++;
            q.push( next );
        }
    }

    if ( cnt < n ) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        for ( long long int i = 1; i < n; i++ ) {
            cout << f[i] + 1 << endl;
        }
    }

    return 0;

}


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

int main() {
    int h, w;
    cin >> h >> w;
    int sy, sx, gy, gx;
    cin >> sy >> sx >> gy >> gx;
    sy--, sx--;
    gy--, gx--;

    vector<string> ms(h);
    rep(i, h) cin >> ms[i];

    vector<vector<int>> cost(h, vector<int>(w, INF));
    deque<pair<int, int>> dque;

    dque.push_front({sy, sx});
    cost[sy][sx] = 0;
    while (!dque.empty()) {
        auto now = dque.front();
        dque.pop_front();

        for (int dy = -2; dy <= 2; ++dy) {
            for (int dx = -2; dx <= 2; ++dx) {
                if (dy == 0 && dx == 0)
                    continue;
                if (now.second + dx < 0 || now.first + dy < 0 || now.second + dx >= w || now.first + dy >= h)
                    continue;
                if (ms[now.first + dy][now.second + dx] == '#')
                    continue;

                if (cost[now.first + dy][now.second + dx] > cost[now.first][now.second] + 1) {
                    cost[now.first + dy][now.second + dx] = min(cost[now.first + dy][now.second + dx], cost[now.first][now.second] + 1);
                    dque.push_back({now.first + dy, now.second + dx});
                }
            }
        }

        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        rep(i, 4) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];

            if (nx < 0 || ny < 0 || nx >= w || ny >= h)
                continue;
            if (ms[ny][nx] == '#' || cost[ny][nx] <= cost[now.first][now.second])
                continue;

            cost[ny][nx] = min(cost[ny][nx], cost[now.first][now.second]);
            dque.push_front({ny, nx});
        }
    }

    // rep(i, 4) {
    //     rep(j, 4) {
    //         cout << cost[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    if (cost[gy][gx] == INF)
        cout << -1;
    else
        cout << cost[gy][gx];
    cout << endl;

    return 0;
}

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

string s;
vector<string> ans;

void dfs(string& s, int n = 1, int mx = 0)
{
  if (n == 0) {
    ans.push_back(s);
    return;
  }
  for (int i = 0; i <= mx; i++) {
    s.push_back('a' + i);
    dfs(s, n - 1, max(mx, i + 1));
    s.pop_back();
  }
}

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

  dfs(s, n);

  for (auto&& e : ans) {
    cout << e << endl;
  }
}


Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define pb push_back
#define all(a) a.begin(),a.end()
#define i64 long long int
int main()
{
    string s;
    cin>>s;
    if(s == "Sunny") pf("Cloudy");
    else if(s == "Cloudy") pf("Rainy");
    else pf("Sunny");
return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;


const long long int mod = 1000000007;
const long long int INF = 99999999999999999;



long long int N,M,res1=0,res2=1;

int main()
{
    cout << fixed << setprecision(18);
    cin>>N;
    while(N!=0){
        res1=N;
        for(long long int i=1;i*i<=2*N;i++){
            if((2*N)%i==0){
                M=i;
                if((2*N/M-M+1)%2==0){
                    res1=(2*N/M-M+1)/2;
                    res2=M;
                }
            }
        }
        cout<<res1<<" "<<res2<<endl;
        cin>>N;

    }
    

}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
inline bool cmp(string a,string b){
	return a<b;
}
int main()
{
	std::ios::sync_with_stdio(false);
	string b[111];
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	cin>>b[i];
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
	cout<<b[i];
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int n, m;
    static int[] l, r, d;
    static String s;
    static int modP = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        l = new int[m];
        r = new int[m];
        d = new int[m];

        Map<Integer, List<E>> map = new HashMap<>();

        for(int i = 0; i < m; i++) {
            l[i] = in.nextInt();
            r[i] = in.nextInt();
            d[i] = in.nextInt();
            E e = new E(l[i], r[i], d[i]);
            List<E> leftList = map.containsKey(l[i]) ? map.get(l[i]) : new LinkedList<E>();
            leftList.add(e);
            map.put(l[i], leftList);

            List<E> rightList = map.containsKey(r[i]) ? map.get(r[i]) : new LinkedList<E>();
            rightList.add(e);
            map.put(r[i], rightList);
        }

        int[] positions = new int[n+1];
        boolean[] visited = new boolean[n+1];

        List<E> init = new LinkedList<E>();
        E e = new E(0, 1, 0);
        init.add(e);
        map.put(0, init);
        visited[0] = true;

        for(int i = 0; i < n + 1; i++) {
            if(!visited[i]) {
                if(!check(i, positions[i], visited, positions, map)) {
                    System.out.println("No");
                    return;
                }
            }
        }

        System.out.println("Yes");
    }

    static boolean check(int id, int position, boolean[] visited, int[] positions, Map<Integer, List<E>> map) {
        positions[id] = position;
        visited[id] = true;

        if(!map.containsKey(id)){
            return true;
        }

        List<E> list = map.get(id);
        for(E e : list) {
            int targetId, targetPos;
            if(e.l == id) {
                targetId = e.r;
                targetPos = positions[id] + e.d;
            }else{
                targetId = e.l;
                targetPos = positions[id] - e.d;
            }

            if(visited[targetId]) {
                if (positions[targetId] != targetPos){
                    return false;
                }
            }else{
                if(!check(targetId, targetPos, visited, positions, map)) {
                    return false;
                }
            }
        }

        return true;
    }
}

class P {
    int x, y;
    P(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class E {
    int l, r, d;
    E(int l, int r, int d) {
        this.l = l;
        this.r = r;
        this.d = d;
    }
}

Measured memory_bytes: 187860
#include <stdio.h>

int main(){
  int a[4], b[4], i, j, hit, blow;
  while(scanf("%d%d%d%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &b[0], &b[1], &b[\
2], &b[3]) != EOF){
    hit = blow = 0;
    for(i = 0;i < 4;i++){
      for(j = 0;j < 4;j++){
        if(a[i] == b[j]){
          if(i == j) hit++;
          else blow++;
          break;
        }
      }
    }
    printf("%d %d\n", hit, blow);
  }
  return 0;
}

Measured memory_bytes: 596
#!/usr/bin/env python3
#dp2 #Frog2

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*n
dp[1] = abs(h[0]-h[1])
for i in range(2,n):
    dp[i] = dp[i-1] + abs(h[i-1] - h[i])
    for j in range(2,k+1):
        if i-j >= 0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i-j] - h[i]))
print(dp[-1])


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

class Program
{
    void solve()
    {
        string[] buf = Console.ReadLine().Split(' ');
        long S = long.Parse(buf[0]);
        long c = long.Parse(buf[1]);
        long ans = 0;

        if (S * 2 > c)
        {
            ans = c / 2;
        }
        else
        {
            ans = S + (c - S * 2) / 4;
        }
        Console.WriteLine(ans);
    }
    public static int Main()
    {
        bool loop = false;
#if ES_DEBUG
        loop = true;
#endif
        do
        {
            new Program().solve();
        } while (loop);
        return 0;
    }
}


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


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    rep(i,n){
        cin >> a[i];
        int j = 0;
        while(a[i] % 2 == 0 && a[i] > 1){
            a[i] /= 2;
            j++;
        }
        b[i] = max(0, j);
    }

    int ans = 0;
    rep(i,n) ans += b[i];

    cout << ans << "\n";


}


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

int h,w,n;
int a[110][110];
int x,y,t;
int m;

int main()
{
    ios::sync_with_stdio(false);
	cin>>h>>w;
	cin>>n;
	m=x=y=1;
	for (int i=1;i<=n;i++) 
	{
		cin>>t;
		while (t--) 
		{
			a[x][y]=i;
			y+=m;
			if (y>w || y<1)
			{
				x++;
				y=y==0?1:w;
				m=-m;
			}
		}
	}
	for (int i=1;i<=h;i++)
	{
		for (int o=1;o<w;o++) cout<<a[i][o]<<" ";
		cout<<a[i][w]<<endl;
	}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define p pair<int, int>
using namespace std;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}

struct Edge {
    int to, cost;
    Edge(int t, int c) : to(t), cost(c) {}
};

bool operator<(const Edge &a, const Edge &b) { return a.cost >= b.cost; }

const int INF = 1e7;

int dist[110][110];
int main() {
    int n, m, s, g1, g2;
    while (cin >> n >> m >> s >> g1 >> g2) {
        if (n == 0 && m == 0) break;
        s--;
        g1--;
        g2--;
        Fill(dist, INF);
        for (int i = 0; i < m; i++) {
            int u, v, c;
            cin >> u >> v >> c;
            u--;
            v--;
            dist[u][v] = c;
        }
        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        int ans = INF;
        for (int i = 0; i < n; i++) {
            ans = min(ans, dist[s][i] + dist[i][g1] + dist[i][g2]);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int main()
{
	int a,b,c,d;
	scanf("%d %d %d",&a,&b,&c);
    d=(a-c)/(b+c);
    printf("%d\n",d);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N; cin >> N;
	map<string, vector<pair<int, int>>> M;

	for(int i=1; i<=N; i++){
		string s; cin >> s;
		int p; cin >> p;
		if(M.count(s) == 0){
			vector<pair<int, int>> v;
			v.push_back(make_pair(p, i));
			M[s] = v;
		}
		else{
			M[s].push_back(make_pair(p, i));
		}
	}
	for(auto itr = M.begin(); itr != M.end(); itr++){
		string k = itr->first;
		auto v = itr->second;
		sort(v.begin(), v.end());
		for(int i=v.size()-1; i>=0; i--){
			auto p = v[i];
			printf("%d\n", p.second);
		}
	}
	return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
int N;
int main(){
	fast;
	cin>>N;
	
	if (N % 1000 == 0) cout<<N % 1000;
	else cout<<1000 - N % 1000;
}


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

int main() {
  int H, W;
  cin >> H >> W;
  int h, w;
  cin >> h >> w;
  int ans = (W - w) * (H - h);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# AGC019
Q, H, S, D = map(int, input().split())
N = int(input())

qhs = min(4 * Q, 2 * H, S)
if N % 2 == 0:
    used = min(2 * qhs, D)
    ans = used * (N // 2)
else:
    if 2 * qhs >= D:
        ans = D * (N // 2) + qhs
    else:
        ans = N * qhs
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#define int long long
#define ll getchar();getchar();return 0;
using namespace std;
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n%i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
int gcd(int x, int y) {
	int ans;
	for (int i = (min(x, y)); i >= 1; i--) {
		if (x%i == 0 && y%i == 0) {
			ans = i;
			break;
		}
	}
	return ans;
}
int yakusuunowa(int n) {
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (n%i == 0)ans += i;
	}
	return ans;
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int ketanowa(int n) {
	int cnt = 0, sum = 0;
	for (int i = 10; i <= n * 10; i *= 10) {
		if (i == 10)cnt += n % i;
		else sum += (n%i - n % (i / 10)) / (i / 10);
	}
	return cnt + sum;
}
pair<int, int>a[114]; int n,cnta,cntb,inf=-10000;
signed main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i].first;
	for(int i=0;i<n;i++)cin>> a[i].second;
	for (int i = 0; i < n; i++) {
		cnta = 0; cntb = 0;
		for (int j = 0; j <= i; j++) {
			cnta += a[j].first;
		}
		for (int k = i; k < n; k++) {
			cntb += a[k].second;
		}
		if (cnta + cntb > inf) {
			inf = cnta + cntb;
		}
	}
	cout << inf << endl;
	ll
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


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

    int sum = 1;
    int cnt = 0;
    while(1){
        if(b <= sum) break;
        sum--;
        sum += a;
        cnt++;
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3568
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    string S;
    cin >> S;
    if (S == "A") cout << "T" << endl;
    if (S == "C") cout << "G" << endl;
    if (S == "G") cout << "C" << endl;
    if (S == "T") cout << "A" << endl;
    return 0;
}


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

#define CIN_ONLY if(1)
struct cww{cww(){
    CIN_ONLY{
        ios::sync_with_stdio(false);cin.tie(0);
    }
}}star;
#define fin "\n"
#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define DEBUG if(0)
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l,T r)
{bool a=l>r;if(a)l=r;return a;}
template <typename T>inline bool chmax(T &l,T r)
{bool a=l<r;if(a)l=r;return a;}
template <typename T>
istream& operator>>(istream &is,vector<T> &v){
    for(auto &it:v)is>>it;
    return is;
}
const int mod=1e9+7;
LL calc(int n){
    vector<LL> x(n);
    cin>>x;
    sort(ALL(x));
    LL sum=0;
    LL res=0;
    FOR(i,1,n){
        sum=sum+i*(x[i]-x[i-1])%mod;
        sum%=mod;
        res=(res+sum)%mod;
    }

    return res;
}
int main(){
    int n,m;
    cin>>n>>m;
    auto x=calc(n);
    auto y=calc(m);
    cout<<x*y%mod<<endl;
    return 0;
}


Measured memory_bytes: 1024
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BinaryHeap, HashMap};

#[allow(dead_code)]
type Graph = Vec<Vec<usize>>;

fn solve(
    last: usize,
    turn: usize,
    dp: &mut Vec<Vec<Option<usize>>>,
    a: &Vec<usize>,
    n: usize,
    w: usize,
) -> usize {
    if dp[last][turn].is_some() {
        return dp[last][turn].unwrap();
    }

    let other = if last == 0 { w } else { a[last - 1] };

    let mut res = (other as i64 - a[a.len() - 1] as i64).abs() as usize;
    let f = if turn == 0 { max } else { min };

    for i in last + 1..n {
        res = f(res, solve(i, 1 - turn, dp, a, n, w));
    }
    dp[last][turn] = Some(res);
    res
}

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

    let mut dp: Vec<Vec<Option<usize>>> = vec![vec![None; 2]; n + 1];
    println!("{}", solve(0, 0, &mut dp, &a, n, w));
}


Measured memory_bytes: 4476
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(a <= c && c <= b) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]
i_Ai = {}
cnt = 0

for i, h in enumerate(A):
	imh = i - h
	if imh in i_Ai:
		cnt += i_Ai[imh]
	iph = i + h
	if iph in i_Ai:
		i_Ai[iph] += 1
	else:
		i_Ai[iph] = 1
print(cnt)

Measured memory_bytes: 40604
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a=0,b,d=-1;
  cin>>n;
  int c[n];
  for(int i=0;i<n;i++){
    cin>>c[i];
    a=max(a,c[i]);
  }
  for(int i=0;i<n;i++){
    if(c[i]!=a){
      if(d<min(c[i],a-c[i])){
        b=c[i];
        d=min(c[i],a-c[i]);
      }
    }
  }
  cout<<a<<" "<<b;
}

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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

#define int int64_t
int a[2*N+2]={0};
int dp[2*N+2]={0};
int32_t  main(){
	IOS;
  int n;cin>>n;
  memset(a,0,sizeof(a));
  vi v;
  forn(i,n){
    int va;cin>>va;
    if(i==0){v.pb(va);continue;}
    if(va==v.back()){
      continue;
    }else v.pb(va);
  }
  //now do dp 
  n=v.size();
  forn(i,n){
    if(i>0){
    dp[i]+=dp[i-1];//without trying to change any suffix
    dp[i]%=mod;
    }else dp[i]=1;
    //now we try to change some suffix to ith character 
    dp[i]=(dp[i]+a[v[i]])%mod;
    if(i>0)
    a[v[i]]=(a[v[i]]+dp[i-1])%mod;
    else a[v[i]]=(a[v[i]]+1)%mod;
  //  cout<<dp[i]<<" ";
    
  }
//  cout<<" dp\n";
  cout<<dp[n-1]<<endl;
  return 0;
}



Measured memory_bytes: 5104
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(ll)(n);++i)
#define _repe3(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define _rrepe2(i,n) for(ll i=(ll)(n);i>=0;i--)
#define _rrepe3(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);i--)
#define rrepe(...) _overload3(__VA_ARGS__,_rrepe3,_rrepe2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

void solve(){
    ll n,m,R;cin>>n>>m>>R;
    vl r(R);rep(i,R)cin>>r[i];
    rep(i,R)--r[i];

    vvl d(n,vl(n,INF));
    rep(i,n)d[i][i]=0;
    rep(i,m){
        ll a,b,c;cin>>a>>b>>c;
        --a;--b;
        d[a][b]=d[b][a]=c;
    }

    rep(i,n)rep(j,n)rep(k,n){
        chmin(d[j][k],d[j][i]+d[i][k]);
    }

    vl a(R);rep(i,R)a[i]=i;
    ll ans=LINF;
    do{
        ll tmp=0;
        rep(i,R-1)tmp+=d[r[a[i]]][r[a[i+1]]];
        chmin(ans,tmp);
    }while(next_permutation(all(a)));

    cout<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].first;
    v[i].second = i + 1;
  }
  sort(v.begin(), v.end());
  for (auto e : v) cout << e.second << ' ';
  cout << endl;
}


Measured memory_bytes: 1664
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
//use proconio::fastout;
use proconio::input;
//use proconio::marker::Chars;
use proconio::marker::Usize1;
//use std::collections::HashSet;
// use std::cmp::*;
//use std::collections::VecDeque;

fn main() {
    input! {
        D:usize,
        C:[i64;26],
        S:[[i64;26];D],
        T:[Usize1;D]
    }
    let mut last = vec![vec![0i64; 26]; D];
    for d in 0..D {
        let i = T[d];
        last[d][i] = d as i64 + 1;
        for e in d + 1..D {
            if T[e] != i {
                last[e][i] = d as i64 + 1;
            } else {
                break;
            }
        }
    }
    let mut x = 0;
    for d in 0..D {
        // d日目にコンテストT[d]を開催する。
        // 満足度が、S[d][T[d]]だけ上昇する。
        // 最後に実施した日 last[d+1以降][T[d]]をdに更新する。
        // 一方、各コンテストについて、C[T[d]] *(d- last[d][T[d]])だけ満足度が下がる。
        let i = T[d];
        x += S[d][i];
        //println!("ss{}", x);
        for j in 0..26 {
            x -= C[j] * (d as i64 + 1 - last[d][j]);
            //println!("C[{}]={} -> {}", j, C[j], x);
        }
        println!("{}", x);
    }
}


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

int main()
{
    int n,i,temp;
    cin >> n;
    long long ans = 0;
    vector<int> number(100000,0);
    for(i = 0;i < n;++i){
        cin >> temp;
        if(temp <= 100000){
            number.at(temp-1)++;
        }else{
            ++ans;
        }
    }
    for(i = 0;i < 100000;++i){
        if(number.at(i) != i+1){
            if(number.at(i) > i+1){
                ans += number.at(i)-i-1;
            }else{
                ans += number.at(i);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
n,x,y=map(int,open(0).read().split())
c=[0]*(n-1)
for i in range(1,n):
  for j in range(i+1,n+1):
    l=min(j-i, abs(x-i)+1+abs(y-j))
    c[l-1]+=1
for c in c:
  print(c)

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

int main(int argc, char const* argv[])
{
    int n,d,x;
    cin>>n>>d>>x;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    int counter=0;
    int b=0;
    for (int i = 0; i < n; i++) {
        b = (d-1)/a[i] + 1;
        counter += b;
    }
    cout<<counter+x<<endl;                                         
    return 0;
}

Measured memory_bytes: 256