akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll x,y;
  cin>>x>>y;
  if(x<y)
    swap(x,y);

  if(x-y>=2)
    cout<<"Alice"<<endl;
  else
    cout<<"Brown"<<endl;
}



Measured memory_bytes: 3608
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	llint H,W,i,h,bgen,sy,sx,ey,ex;cin>>H>>W>>sy>>sx>>ey>>ex;
	llint ycos=1333,xcos=1333,ans=1,gen=1;
	ycos=abs(sy-ey);
	if(ycos>H-ey){ycos=H-ey;gen=1;}else if(ycos==H-ey){gen++;}
	if(ycos>1+ey){ycos=1+ey;gen=1;}else if(ycos==1+ey){gen++;}
	ans*=gen;gen=1;
	xcos=abs(sx-ex);
	if(xcos>W-ex){xcos=W-ex;gen=1;}else if(xcos==W-ex){gen++;}
	if(xcos>1+ex){xcos=1+ex;gen=1;}else if(xcos==1+ex){gen++;}
	ans*=gen;
	llint fra[1333];
	fra[0]=1;
	for(i=1;i<1333;i++){fra[i]=fra[i-1]*i%mod;}
	llint gya[1333];
	gya[1332]=1;bgen=fra[1332];
	for(h=0;h<30;h++){
		if((1<<h)&(mod-2)){gya[1332]*=bgen;gya[1332]%=mod;}
		bgen*=bgen;bgen%=mod;
	}
	for(i=1332;i>0;i--){gya[i-1]=gya[i]*i%mod;}
	ans*=fra[ycos+xcos];ans%=mod;
	ans*=gya[ycos];ans%=mod;
	ans*=gya[xcos];ans%=mod;
	cout<<ycos+xcos<<" "<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3224
import bisect

n,*a = map(int, open(0).read().split())
if n == 2:
    print(*a)
else:
    a.sort()
    f = a[-1]
    h = f / 2
    bs = bisect.bisect_left(a,h)
    if abs(a[bs-1]-h) >= abs(a[bs]-h):
        s = a[bs]
    else:
        s = a[bs-1]
    print(f,s)


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

const int DIM = 1e2 + 5;

int dst[DIM][DIM];
tuple<int, int, int> edg[DIM * 10];

int main( void ) {
    
    int n, m;
    cin >> n >> m;
    
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= n; j ++ )
        if( i != j )
            dst[i][j] = 1e9;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y, z;
        cin >> x >> y >> z;
        
        edg[i] = tie( x, y, z );
        dst[x][y] = dst[y][x] = z;
    }
    
    for( int k = 1; k <= n; k ++ )
    for( int i = 1; i <= n; i ++ )
    for( int j = 1; j <= n; j ++ )
        dst[i][j] = min( dst[i][j], dst[i][k] + dst[k][j] );
    
    int ans = 0;
    for( int k = 1; k <= m; k ++ ) {
        bool ok = true;
        int x, y, z;
        
        tie( x, y, z ) = edg[k];
        for( int i = 1; i <= n; i ++ )
        for( int j = i + 1; j <= n; j ++ )
            if( dst[i][j] == dst[i][x] + z + dst[y][j] ||
                dst[i][j] == dst[i][y] + z + dst[x][j] )
                ok = false;
        
        ans += ok;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
s=[list(map(int,input().split()))[1:] for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    tmp=[]
    for j in range(n):
        if (i>>j)&1:
            tmp.append(j+1)
    for k in range(m):
        if len(set(tmp)&set(s[k]))%2!=p[k]:
            break
    else:
        ans+=1
print(ans)

Measured memory_bytes: 68128
//#pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define mod 998244353
//#define int long long
#define inf 200000000
const int maxnodes=1005;
#define ll long long
#define N 501
#define EPS 0.01


int32_t main()
{
    IOS;
   
    int n;
    string s;
    cin >> s;
    n = s.length();
    int wins = 0;
    for(int i = 0;i < n;i++)
    {
        if(s[i] == 'o')
            wins++;
    }
    if(wins + (15 - n) >= 8)
        cout << "YES";
    else
        cout << "NO";




    
    return  0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}

int main() {
	//file();
	fast();
	string str; cin >> str;
	if (str[2] == str[3] && str[4] == str[5])
		cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
// atcoder/abc051/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

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

  string s;
  while (cin >> s) {
    replace(s.begin(), s.end(), ',', ' ');
    cout << s << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100007;
int n,m,k,ans1,ans2;
bool h[maxn];
char str[maxn];

int main(){
    //freopen("in.txt","r",stdin);
    scanf("%s",str);
    int len = strlen(str);
    ans1 = ans2 = 0;
    char bef,aft;

    if(len == 1){
        printf("0\n");
        return 0;
    }
    bef = str[0];
    for(int i = 1;i < len;i++)
    {
        aft = str[i];
        if(bef == aft){
            ans1++;
            //printf("ans 1 i = %d,str[%d] = %c\n",i,i,str[i]);
            if(aft == '1')bef = '0';
            else bef = '1';
        }
        else bef = aft;
    }
    bef = str[len -1];
    for(int i = len - 2;i >= 0;i--)
    {
        aft = str[i];
        if(bef == aft){
            ans2++;
            //printf("ans 2 i = %d,str[%d] = %c\n",i,i,str[i]);
            if(aft == '1')bef = '0';
            else bef = '1';
        }
        else bef = aft;
    }
    printf("%d\n",min(ans1,ans2));
    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <cmath>

long long calc(int k) {
    long long ans = 100;
    while (k--) ans *= 1.01;
    return ans;
}

int main() {
    long long x;
    scanf("%lld", &x);
    int l = 0, r = 3760, mid, tm = log2(3760) + 100, cnt = 0;
    while(l < r) {
        ++cnt;
        if(cnt > tm) break;
        mid = l + r >> 1;
        if(calc(mid) > x) r = mid;
        else l = mid;
    }
    printf("%d", calc(l) >= x ? l : r);
    return 0;
}


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

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

    if(S[a]!='-'){
        cout << "No" << endl;
        return 0;
    }

    for(int i=0; i<S.size(); i++){
        if(i==a) continue;
        if(S[i]=='-'){
          cout << "No" << endl;
          return 0;
        }
    }

    if(S.size()-(a+1)==b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

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

	double a = 0;
	for( int i = 1; i <= N; i++ ) {
		if( i % 2 ) a++;
	}
	double ans = a / N;

	cout << fixed << setprecision(12) << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
inline int readInt() {int x; cin >> x; return x;}
inline char readChar() {char c; cin >> c; return c;}
inline string readString() {string s; cin >> s; return s;}

int32_t main()
{
	//freopen("input.txt", "r", stdin);
	IOS;
	
	int n = readInt();
	int d = readInt();
	int ans = 0;

	for(int i = 0 ; i < n ; i++) {
		int x, y; cin >> x >> y;
		int distance = x*x + y*y;
		if(d*d >= distance) ++ans;
	}	

	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>

int main(void) {
	int card[4][13];
	int n, num;
	char pic;
	
	//二次元配列を0で初期化する
	for(int i = 0; i < 4; i++) {
	    for(int j = 0; j < 13; j++) {
	        card[i][j] = 0;
	    }
	}
	
	//持っているカードの枚数を入力する
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
	    scanf("%c %d", &pic, &num);
	    //該当する箇所の値を1にする
	    //スペード(S)の場合
	    if(pic == 'S') {
	        card[0][num - 1] = 1;
	    }
	    //ハート(H)の場合
	    else if(pic == 'H') {
	        card[1][num - 1] = 1;
	    }
	    //クローバー(C)の場合
	    else if(pic == 'C') {
	        card[2][num - 1] = 1;
	    }
	    //ダイヤ(D)の場合
	    else if(pic == 'D') {
	        card[3][num - 1] = 1;
	    }
	    else{
	        i--;
	    }
	}
	
	//足りないカードを出力する
	for(int i = 0; i < 4; i++) {
	    for(int j = 0; j < 13; j++) {
	        if(card[i][j] == 0) {
	            if(i == 0) {
	                printf("%c %d\n", 'S', j + 1);
	            }
	            else if(i == 1) {
	                printf("%c %d\n", 'H', j + 1);
	            }
	            else if(i == 2) {
	                printf("%c %d\n", 'C', j + 1);
	            }
	            else if(i == 3) {
	                printf("%c %d\n", 'D', j + 1);
	            }
	        }
	    }
	}
	return 0;
}


Measured memory_bytes: 2048
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    string s;cin>>s;
    int n=s.length();
    int c=999;
    for(int i=0;i<=n-3;i++)
    {
        int now=100*(s[i]-'0')+10*(s[i+1]-'0')+(s[i+2]-'0');
        //cout<<now-753<<endl;
        chmin(c,abs(now-753));
    }
    cout<<c<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 256
import java.util.*;
public class Main {

    public static void main(String[] args) {        
        Scanner s = new Scanner(System.in);
        int[] a = new int[5];
        for(int i = 0 ; i < 5 ; i++)
            a[i] = s.nextInt();      
        Arrays.sort(a);
        for(int j = a.length - 1 ; j > 0 ; j--)
            System.out.print(a[j] + " ");
        System.out.println(a[0]);
    }
}

Measured memory_bytes: 12000
import math
import itertools
import statistics
#import collections
n = int(input())
s = input()

amari = 0
plus = 0

for i in range(n):
    if s[i]=="(":
        plus += 1
    else:
        if plus <= 0:
            amari +=1
        else:
            plus -= 1

for i in range(amari):
    print("(", end="")

print(s, end="")

for i in range(plus):
    print(")", end="")




Measured memory_bytes: 5144
import java.util.*;
class Main{
    public static void main(String[] a){
      int n = 10;
      int[] num = new int[n];

      Scanner stdin = new Scanner(System.in);
      for ( int i = 0; i < n; i++ ){
        num[i] = stdin.nextInt();
      }

      boolean flag = true;
      while (flag){
        flag = false;
        for ( int j = n-1; j >= 1; j-- ){
          if ( num[j] > num[j-1] ){
            int tmp = num[j];
            num[j] = num[j-1];
            num[j-1] = tmp;
            flag = true;
          }
        }
      }

      for ( int i = 0; i < 3; i++ ){
        System.out.println(num[i]);
      }
    }
}

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

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

    ll ans = 0;
    ll j = 0;
    rep(i, s.size()){
        if(s[i] == 'W'){
            ans += i-j;
            j++;
        }
    }
    cout << ans << endl;

    return 0;
}


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

 using namespace std;
 int main() {
   string S, ans;
   int i;

   cin >> S;
   ans = "No";

   for (i = 0; i < S.length() - 1; i++) {
     if (S.at(i) == 'A' && S.at(i + 1) == 'C') {
       ans = "Yes";
       break;
     }
   }
   cout << ans << endl;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    multiset<int> ms;
    ms.insert(-100);
    rep(i, 0, N)
    {
        auto it = ms.lower_bound(A[i]);
        if (it == ms.begin())
        {
            ms.insert(A[i]);
        }
        else
        {
            --it;
            ms.erase(it);
            ms.insert(A[i]);
        }
    }
    cout << ms.size() << endl;
}


Measured memory_bytes: 5376
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define inf 1e+9
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

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

    ll n,sum=0,sum1=0,sum2=0,ans=0;
	cin >> n;
	ll a[n];
	rep(i,n){
		cin >> a[i];
		sum += a[i];
		int b=a[0];
		if(a[i]==0){
			ans++;
		}
		else{
			sum1++;
		}
		// if(a[i]%2==0){
		// 	sum1+=a[i];
		// }
		// else{ 
		// 	sum2+=a[i];
		// }
	}

	if(sum%2==0 && sum%n==0 || ans==n){
		cout << "Yes" << endl;
	}
	else if(sum==0){
		cout << "Yes" << endl;
	}
	else if(ans==n/3 && sum1==2*n/3){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	// if(sum%2==0 && sum%n==0 || ans==n){
	// 	cout << "Yes" << endl;
	// }
	// else{
	// 	cout << "No" << endl;
	// }	
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    ll a[100000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    bool inc = false, dec = false;
    if (a[1] - a[0] > 0) {
        inc = true;
    }
    if (a[1] - a[0] < 0){
        dec = true;
    }
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i - 1]) {
            inc = true;
        }
        if (a[i] < a[i - 1]) {
            dec = true;
        }
        if (inc && dec) {
            cnt++;
            inc = false;
            dec = false;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1152
/********   In the name of Allah, the most gracious, the most merciful ********/
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, k;
    cin >> n >> k;
    int h[n], dp[n],mx = 1e9+10;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        dp[i] = mx;
    }
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for (int i = 2; i < n; i++)
    {
        for (int j = 1; j <= k && i-j >=0;j++)
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
    }
    cout << dp[n - 1] << endl;
}
/*
3 4
3 2 1 3
1 9 2 3
9 1 5 4
*/


Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {

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

		int N = s.nextInt();
		int[] C = new int[N];
		int[] S = new int[N];
		int[] F = new int[N];
		int[] x = new int[N];
		x[N - 1] = 0;
		int sumC = 0;
		int sumI = 0;
		for (int i = 0; i < N - 1; i++) {
			C[i] = s.nextInt();
			S[i] = s.nextInt();
			F[i] = s.nextInt();
		}
		C[N - 1] = 0;
		S[N - 1] = 0;
		F[N - 1] = 0;

		for (int i = 0; i < N - 1; i++) {
			sumI = C[i] + S[i];
			for (int j = i + 1; j < N - 1; j++) {
				if (sumI < S[j]) {
					sumI = S[j];
				} else if (sumI % F[j] != 0) {
					int update = 1;
					while (sumI > S[j] + F[j] * update) {
						++update;
					}
					sumI = S[j] + F[j] * update;
				}

				sumI += C[j];

			}
			x[i] = sumI;
		}

		for (int i = 0; i < N; i++) {
			System.out.println(x[i]);
		}

	}
}


Measured memory_bytes: 27620
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
)

var sc *bufio.Scanner

const BufferSize = 1024

func nextString() string {
	if !sc.Scan() {
		panic(nil)
	}
	return sc.Text()
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	s := nextString()
	t := nextString()

	si := make([][]int, 26)
	for i := range s {
		a := rune(s[i]) - rune(`a`[0])
		si[a] = append(si[a], i+1)
	}
	debugf("%v\n", si)

	ans := uint64(0)
	idx := 0
	for i := range t {
		a := rune(t[i]) - rune(`a`[0])
		if len(si[a]) == 0 {
			_, _ = fmt.Fprint(writer, "-1")
			return
		}
		k := sort.Search(len(si[a]), func(k int) bool { return idx < si[a][k] })
		debugf("find: %s, idx: %d, k: %d from %v\n", string(t[i]), idx, k, si[a])
		/*
			j := 0
			for si[a][j] <= idx {
				if j == len(si[a])-1 {
					idx = 0
					ans += uint64(len(s))
					debugf("reset: %s, %d, %d\n", string(t[i]), idx, ans)
					j = 0
					break
				}
				j++
			}
			idx = si[a][j]
		*/
		if k == len(si[a]) {
			idx = 0
			ans += uint64(len(s))
			k = 0
		}
		idx = si[a][k]
		debugf("index: %s, %d\n", string(t[i]), idx)
	}

	_, _ = fmt.Fprintf(writer, "%d", ans+uint64(idx))
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 5504
#include<iostream>

int n, s;

int solve(int ind, int n, int s){
	if (ind == 10){
		if (n == 0 && s == 0)return 1;
		else return 0;
	}
	return solve(ind + 1, n - 1, s - ind) + solve(ind + 1, n, s);
}

int main(){
	while (std::cin >> n >> s , n){
		std::cout << solve(0,n,s) << std::endl;
	}

}

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

int main() {
    int x;
    cin >> x;
    
    int ans = 1;
    for (int i = 2; i <= sqrt(x); i++) {
        int can = 1;
        while (can * i <= x) can *= i;
        ans = max(ans, can);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
# Author: cr4zjh0bp
# Created: Thu Mar 12 20:36:21 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
dp = [0] * (N + 1)
dp[0] = 2
dp[1] = 1

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N])

Measured memory_bytes: 3064
#include <cstdio>
#include <utility>
#include <stack>
using namespace std;

#define gcu getchar_unlocked
#define ii inline int in
#define is inline bool scan
ii(int c) {
	int n = 0;
	bool minus = false; if (c == '-') minus = true, c = gcu();
	do {n = 10 * n + (c - '0'), c = gcu();} while (c >= '0');
	//return n; }
	return minus ? -n : n; }
ii() {return in(gcu());}
is(int &n){int c=gcu();return c==EOF?false:(n=in(c),true);}
is(char &c){c=gcu();gcu();return c!=EOF;}
//is(string &s){int c;
//	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#undef ii
#define pcu putchar_unlocked
template <typename T>
void out(T n) {
	static char buf[20];
	char *p = buf;
	if(n < 0) pcu('-'), n *= -1;
	if (!n) *p++ = '0';
	else while (n) *p++ = n % 10 + '0', n /= 10;
	while (p != buf) pcu(*--p); }
void out(const char *s){while(*s)pcu(*s++);}
void out(char c){pcu(c);}
//void out(string &s){for (char c: s) pcu(c);}
template <typename head, typename... tail>
void out(head&& h, tail&&... t){out(h);out(move(t)...);}
//template <typename T>
//void out(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);out('\n');}
#undef svo

int days(int y, int m, int d) {
	y--, m--, d--;
	return y / 3 * (2 * 5 * 39 + 10 * 20) + y % 3 * 5 * 39
		+ m * 20 - (y % 3 == 2 ? 0 : m / 2)
		+ d;
}

int main() {
	int n = in(), a = days(1000, 1, 1);
	while (n--) {
		int y = in(), m = in(), d = in();
		out(a - days(y, m, d), '\n');
	}
}


Measured memory_bytes: 2520
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author : gaurav.ss
 * @since : 16/02/20
 **/
 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        List<String> list= new ArrayList<>();
        Map<String, Integer> map= new HashMap<>();
        int max=0;
        for(int i=0;i<n;i++){
            String s=in.next();
            if(map.containsKey(s)){
                int v= map.get(s);
                v++;
                if(v>max){
                    max=v;
                }
                map.put(s, v);
            }else{
                map.put(s,1);
                if(1>max){
                    max=1;
                }
            }
        }
        for(Map.Entry<String, Integer> e: map.entrySet()){
            if(e.getValue()==max){
                list.add(e.getKey());
            }
        }
        Collections.sort(list);
        for(String s: list)
            System.out.println(s);

    }
}


Measured memory_bytes: 81384
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    heapify(ab)
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        heappush(ab, (a,b))
    
    ans = 0
    pq = []
    heapify(pq)
    for i in range(1,M+1):
        while True:
            if len(ab) == 0 or ab[0][0] != i:
                break
            a,b = heappop(ab)
            heappush(pq, -b)
            
        if len(pq) > 0:
            ans = ans + (heappop(pq) * (-1))
        
    
    print(ans)
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 84184
n,k = map(int,input().split())
r,s,p = map(int,input().split())
st=input()
for i in range(len(st)-1):
    if i + k > len(st)-1:
        break
    elif st[i] == st[i+k]:
        st = st[:i+k]+'n'+st[i+k+1:]
win = r*st.count('s')+s*st.count('p')+p*st.count('r')
print(win)

Measured memory_bytes: 3436
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int n = sc.nextInt();
        int ans = 0;
        if (n >= 105) {
          ans++;
        }
        if (n >= 135) {
          ans++;
        }
        if (n >= 165) {
          ans++;
        } 
        if (n >= 189) {
          ans++;
        } 
        if (n >= 195) {
          ans++;
        }

		// 出力
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include<bitset>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	ll a[200001];
	ll za[200001];
	set<ll> pl,mi;
	scan(N);
	rep(i,N){
		scan(a[i]);
		za[a[i]]=i;
	}
	pl.insert(-1);
	pl.insert(N);
	mi.insert(1);
	mi.insert(-N);
	ll ans=0;
	rep1(i,N){
		auto itr=pl.lower_bound(za[i]);
		auto itr2=mi.lower_bound(-za[i]);
		ll migi=(*itr)-za[i];
		ll hidari=(*itr2)+za[i];

		ans+=migi*hidari*i;
		pl.insert(za[i]);
		mi.insert(-za[i]);
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 22144
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a>0) cout<<"Positive"<<endl;
	else if(b>=0) cout<<"Zero"<<endl;
	else if((b-a)&1) cout<<"Positive"<<endl;
	else cout<<"Negative";
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
 
MAX = pow(10,6)
#L = get_sieve_of_eratosthenes(MAX)
 
def factorization(n):
    arr = []
    temp = n
    if temp%2 == 0:
      cnt = 0
      while temp%2 == 0:
        cnt += 1
        temp//=2
      arr.append(2)
    for i in range(3, int(-(-n**0.5//1))+1,2):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
 
    if temp!=1:
        arr.append(temp)
 
    return arr
 
#XX = factorization(121)
#print(XX)
import math
N = int(input())
A = list(map(int,input().split()))
GCD = math.gcd(A[0],A[1])
for i in range(2,N):
  GCD = math.gcd(GCD,A[i])
  if GCD == 1:
    break
if GCD != 1:
  print("not coprime")
  exit()
#A.sort()
SET = set([])
for x in A:
  SL = factorization(x)
  for yakusu in SL:
    if yakusu not in SET:
      SET.add(yakusu)
    else:
      print("setwise coprime")
      exit()
print("pairwise coprime")

Measured memory_bytes: 174596
import sys
input=sys.stdin.readline
n=int(input())
a_list=[int(input()) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)


Measured memory_bytes: 45532
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSharp_TestCode
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b;
            string[] input = Console.ReadLine().Split();
            a = int.Parse(input[0]);
            b = int.Parse(input[1]);

            if (a + b >= 10) Console.WriteLine("error");
            else Console.WriteLine(a+ b);

        }

    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
typedef long long ll;
#define vll vector<long long> 
#define pll pair<ll,ll>
#define f(i,a,b) for(long long i=a;i<b;i++)
#define F first
#define S second
#define pb(i) push_back(i)
#define mp(x,y) make_pair(x,y)
#define all(v)  (v).begin(),(v).end()
#define sz 1001
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int main(){
	FIO;ll n;cin>>n;
	vll v(n),dp(n,1e9);
	f(i,0,n) cin>>v[i];
	dp[0] = 0; dp[1] = abs(v[1]-v[0]);
	f(i,2,n){
		ll a = abs(v[i]-v[i-1])+dp[i-1];
		ll b = abs(v[i]-v[i-2])+dp[i-2];
		dp[i] = min(a,b);
	}
	cout<<dp[n-1]<<"\n";
}

Measured memory_bytes: 4768
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
//**デバッグ準備**//
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail>
void debug_out(Head h, Tail... t) {
	cerr << " " << h;
	if (sizeof...(t) > 0) cerr << " :";
	debug_out(t...);
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> vec) {
	for (size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	return os;
}
ll ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//bitSearch, bitList, gcdlcm, isPrime, primeFactorize, Npow, divisor, modinv, dfs, bfs, eratos//
//dijkstra, WarshallFloyd, BellmanFord, UnionFind, COM, digitDP ,RMQ//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z, R;
ll MOD = 1000000007; ll INF = 1LL << 62; ll ans = INF; ll z = 0, o = 1;
vl flag, color, D; vll path;
int main() {
	string S;
	cin >> S;
	vl C(26);
	vl D(26);
	for (i = 0; i < 26; i++) {
		C[i] = -1;
		D[i] = -1;
	}
	N = S.length();
	for (i = 0; i < N; i++) {
		D[S[i]-'a'] = max(D[S[i]-'a'], i - C[S[i] - 'a'] - 1);
		C[S[i] - 'a'] = i;
	}
	for (i = 0; i < 26; i++) {
		D[i] = max(D[i], N - 1 - C[i]);
	}
	ans = INF;
	debug(D);
	for (i = 0; i < 26; i++) {
		if (D[i] != -1) {
			ans = min(ans, D[i]);
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10 ** 9
def dfs(cur, a, b, c):
  if cur == N:
    return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
  ret0 = dfs(cur + 1, a, b, c)
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10
  return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

Measured memory_bytes: 43996
M,D = map(int, input().split())

def search(m,D):
    box = []
    for j in range(2,10):
        if m%j == 0 and 9 >= m/j >= 2:
            a = j*10+int(m/j)
            if a <= D:
                box.append(j*10+int(m/j))
    return box

c = 0
for m in range(1,M+1):
    box = search(m,D)
    c += len(box)

print(c)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(void) {
	int N,M;
	cin >> N;
	map<string,int> card;
	for (int i = 0; i < N; ++i) {
		string blue;
		cin >> blue;
		++card[blue];
	}
	cin >> M;
	for (int i = 0; i < M; ++i) {
		string red;
		cin >> red;
		--card[red];
	}

	int res = 0;
	for (auto itr = card.begin(); itr != card.end(); ++itr) {
		res = max(itr->second,res);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,count=0;
  cin>>n;
  long long x=sqrt(n);
  float z=sqrt(n);
  long long sum=0,maximum=0;
  if(x!=z){
  	x=x+1;
  }
  for(long long i=1;i<=x;i++){
  	if(n%i==0){
  		long long j=n/i;
  		sum=i+j;
  		count++;
  		if(count==1){
  			maximum=sum;
		  }
		  else if(sum<maximum){
		  	maximum=sum;
		  }
  		
  		
	  }
  }
  cout<<maximum-2<<endl;

  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	
	ll n;
	cin>>n;
	string ans="";
	while(n>0)
	{
		int x=n%26;
		if(x!=0)
		ans=char(x+96)+ans;
		else
		ans='z'+ans;
		if(x!=0)
		n-=x;
		else
		n-=26;
		n/=26;
	}
	cout<<ans<<endl;
	return 0;
}

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

struct Node {
    int key;
    struct Node *right, *left, *parent;
};
typedef struct Node Node;

Node *root, *NIL;

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;
    
    z = (Node *)malloc(sizeof(Node));
    z->key   = k;
    z->left  = NIL;
    z->right = NIL;
    
    while(x != NIL) {
        y = x;
        if(z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    
    z->parent = y;
    if(y == NIL) {
        root = z;
    } else {
        if( z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}

void inorder(Node *u) {
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u) {
    if(u == NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
    
int main(void) {
    int n, i, x;
    char com[16];
    scanf("%d",&n);
    
    for(i=0;i<n;i++) {
        scanf("%s",com);
        if(!strcmp(com,"insert")) {
            scanf("%d",&x);
            insert(x);
        } else if(!strcmp(com,"print")) {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


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

const int MOD = 1000000007;
const int MAXN = 3005;
int n, q;
int A[MAXN];
pair<int, int> Q[MAXN];
vector<int> swapTime[MAXN];
vector<int> swapWith[MAXN];
int nxt[MAXN][MAXN];
int dp[MAXN][2][MAXN][2];
int pw2[MAXN];

int whichSide(int e, int x) {
	if (Q[e].first == x) return 0;
	else return 1;
}
int sol(int i, int j, int x, int y) {
	int e1, e2;
	e1 = swapTime[i][x];
	e2 = swapTime[j][y];
	if (q == e1 && q == e2) {
		return (i > j) ? 1 : 0;
	}
	int a, b, c, d;
	if (e1 <= e2) {
		a = e1;
		b = whichSide(e1, i);
		c = j;
		d = 0;
	} else {
		a = e2;
		b = whichSide(e2, j);
		c = i;
		d = 1;
	}
	if (dp[a][b][c][d] != -1) return dp[a][b][c][d];
	int ans = 0;
	if (e2 < e1) {
		int dis = min(e1, swapTime[j][y+1]) - e2 - 1;
		ans = (pw2[dis] * 1ll * sol(i, j, x, y + 1)) % MOD;
		int nj = swapWith[j][y];
		int ny = nxt[nj][e2 + 1];
		dis = min(swapTime[nj][ny], e1) - e2 - 1;
		ans += (pw2[dis] * 1ll * sol(i, nj, x, ny)) % MOD;
		ans %= MOD;
		return dp[a][b][c][d] = ans;
	}
	if (e2 > e1) {
		int dis = min(e2, swapTime[i][x + 1]) - e1-1;
		ans = (pw2[dis] * 1ll * sol(i, j, x+1, y)) % MOD;
		int ni = swapWith[i][x];
		int nx = nxt[ni][e1 + 1];
		dis = min(e2, swapTime[ni][nx]) - e1 - 1;
		ans += (pw2[dis] * 1ll * sol(ni, j, nx, y)) % MOD;
		ans %= MOD;
		return dp[a][b][c][d] = ans;
	}
	int dis = min(swapTime[i][x+1], swapTime[j][y+1]) - e1 - 1;
	ans = (pw2[dis] * 1ll * sol(i, j, x + 1, y + 1)) % MOD;
	ans += (pw2[dis] * 1ll * sol(j, i, y + 1, x + 1)) % MOD;
	ans %= MOD;
	return dp[a][b][c][d] = ans;
}

int main() {
	memset(dp, -1, sizeof(dp));
	pw2[0] = 1;
	for (int i = 1; i < MAXN; i++) {
		pw2[i] = (pw2[i-1] * 2) % MOD;
	}
	scanf("%d %d", &n, &q);
	for (int i = 0; i < n; i++) scanf("%d", A + i);
	for (int i = 0; i < q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--;
		y--;
		swapTime[x].push_back(i);
		swapWith[x].push_back(y);
		swapTime[y].push_back(i);
		swapWith[y].push_back(x);
		Q[i] = {x, y};
	}
	for (int i = 0; i < n; i++) {
		swapTime[i].push_back(q);
		int k = 0;
		for (int j = 0; j < swapTime[i].size(); j++) {
			while (k <= swapTime[i][j]) {
				nxt[i][k] = j;
				k++;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (A[i] == A[j]) continue;
			int res = (pw2[min(swapTime[i][0], swapTime[j][0])] * 1ll * sol(i, j, 0, 0)) % MOD;
			if (A[i] < A[j]) ans += res;
			else {
				ans += (pw2[q] - res + MOD) % MOD;
			}
			ans %= MOD;
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 177280
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct UnionFind{
  Int n;
  vector<Int> r,p;
  UnionFind(){}
  UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};


signed main(){
  Int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  for(Int i=0;i<m;i++){
    Int a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a,b);
  }
  const Int SQ = 400;
  vector<Int> c(SQ,0);
  vector<Int> p;
  for(Int i=2;i<n;i++){
    if(uf.find(i)==uf.find(0)) continue;
    if(uf.find(i)==uf.find(1)) continue;
    if(uf.find(i)!=i) continue;
    if(uf.r[i]<SQ) c[uf.r[i]]++;
    else p.push_back(uf.r[i]);
  }
  vector<Int> dp(n+1,-1);
  dp[0]=0;
  for(Int i=1;i<SQ;i++){
    if(!c[i]) continue;
    for(Int j=0;j<=n;j++){
      if(dp[j]>=0){
	dp[j]=c[i];
      }else if(j<i||dp[j-i]<=0){
	dp[j]=-1;
      }else{
	dp[j]=dp[j-i]-1;
      }
    }
  }
  vector<Int> dp2(n+1,0);
  for(Int i=0;i<=n;i++) dp2[i]=dp[i]>=0;
  for(Int i=0;i<(Int)p.size();i++){
    for(Int j=n-p[i];j>=0;j--){
      dp2[j+p[i]]|=dp2[j];
    }
  }
  auto calc=[](Int x,Int y){
    return x*(x-1)/2+y*(y-1)/2;
  };
  
  Int ans=m;
  Int x=uf.r[uf.find(0)];
  Int y=uf.r[uf.find(1)];
  Int z=n-(x+y);
  for(Int i=0;i<=n;i++){
    if(!dp2[i]) continue;
    ans=max(ans,calc(x+i,y+(z-i)));
  }
  cout<<ans-m<<endl;
  return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long a1,a2,a3,a4,n,ans;
int main()
{
    cin>>a1>>a2>>a3>>a4;
    cin>>n;
    a2=min(a2,a1*2);
    a3=min(a2*2,a3);
    a4=min(a4,a3*2);
    if(n%2==1) ans+=a3;
    ans+=(n/2)*a4;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main (){
    int n,q;
    cin>>n>>q;
    vector<priority_queue<int>> st(n);
    rep(i,0,q){
        int cmd;cin>>cmd;
        if(cmd==0){
            int t,x;cin>>t>>x;
            st[t].push(x);
        }else  if(cmd==1){
            int t;cin>>t;
            if(!st[t].empty())cout<<st[t].top()<<endl;
        }else {
            int t;cin>>t;
            if(!st[t].empty())st[t].pop();
        }
    }
    

}



/*

*/


Measured memory_bytes: 4072
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

const int mx = 200000 + 50;
set<int> tt;

int main(){
    int n;
    long long t;
    while(~scanf("%d", &n)){
        scanf("%lld", &t);
        // printf("---%d\n", t);
        long long ans = 0;
        for(int i = 0, x; i < n; ++i){
            scanf("%d", &x);
            tt.insert(x);
        }
        int last = -1;
        for(set<int>::iterator it = tt.begin(); it != tt.end();){
            if(last < 0){
                last = *it;
                continue;
            }
            if(*it < last + t){
                ans += *it - last;
            }
            else{
                ans += t;
            }
            last = *it;
            ++it;
            if(it == tt.end()){
                ans += t;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 9600
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus >= 201703L
#        pragma GCC target("avx2")
#    else
#        pragma GCC target("avx")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    Ld n;
    cin >> n;

    for (int i = 6; i >= 0; i--) {
        if (powl(2, i) <= n) {
            cout << (Int)powl(2, i) << endl;
            break;
        }
    }

    return 0;
}


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

int main(){
    ll n;
    cin >> n;
    vector<ll> p1(n),p2(n);
    rep(i,n){
        ll x,y;
        cin >> x >> y;
        p1[i]=x-y;
        p2[i]=x+y;
    }
    sort(p1.begin(),p1.end());
    sort(p2.begin(),p2.end());
    cout << max(p1[n-1]-p1[0],p2[n-1]-p2[0]) << endl;

}

Measured memory_bytes: 6424
n = input()
d = dict()
M = 1
for i in range(n):
  w = raw_input()
  if w in d:
    d[w] += 1
    M = max(d[w], M)
  else:
    d[w] = 1
l = []
for k in d:
  if d[k] == M:
    l.append(k)
l = sorted(l)
for one in l:
  print (one)

Measured memory_bytes: 35760