문제
Hudson River Trading(HRT)은 뛰어난 수학, 기술적 역량을 활용하여 거래 전략을 설계하는 퀀트 트레이딩 회사이다. HRT는 엔지니어와 연구자들이 한 팀을 이뤄 어려운 문제를 해결하며, 글로벌 금융 시장에서 매일 수백만 주의 주식을 거래한다.
HRT의 신입 알고리즘 개발자는 새로 설계한 거래 전략을 따르는 시장조성(market-making) 엔진을 개발한 뒤, 그 엔진의 안정성을 평가하고자 한다. 시장조성 엔진은 주식을 보유하지 않은 가상의 계좌를 이용하여 거래를 시작하며, $N$개의 연속된 매매 시점(틱)에 아래와 같은 전략을 따라 거래한다.
- $i$번째 매매 시점에 엔진은 $a_i$ 이상 $b_i$ 이하의 정수 하나를 선택한다. 선택한 정수가 양수라면 그만큼 주식을 매수하고, 음수라면 선택한 정수의 절댓값만큼 주식을 매도하고, 0ドル$이라면 주식을 매매하지 않는다. 이 때 보유한 주식이 부족해도 매도가 가능하며, 이 경우 보유 주식의 수는 음수가 된다.
- $i$번째 매매 직후 보유 주식이 0ドル$주라면, 해당 전략이 포지션 노출을 최소화하여 위험성을 완화하고 시장 안정성에 기여했다고 평가하여 시장조성 엔진의 안정성이 $x_i$만큼 증가한다.
- 수수료 또는 슬리피지 등 다른 요소는 모두 무시한다.
총 $N$번의 매매를 모두 마쳤을 때, 신규 개발한 시장조성 엔진이 달성할 수 있는 안정성의 최댓값을 구해보자.
출력
총 $N$번의 매매를 모두 마쳤을 때, 신규 개발한 시장조성 엔진이 달성할 수 있는 안정성의 최댓값을 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDU3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmRjXHVjN2E1XHVjODcwXHVjMTMxXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5IdWRzb24gUml2ZXIgVHJhZGluZyhIUlQpXHVjNzQwIFx1YjZmMFx1YzViNFx1YjA5YyBcdWMyMThcdWQ1NTksIFx1YWUzMFx1YzIyMFx1YzgwMSBcdWM1ZWRcdWI3YzlcdWM3NDQgXHVkNjVjXHVjNmE5XHVkNTU4XHVjNWVjIFx1YWM3MFx1Yjc5OCBcdWM4MDRcdWI3YjVcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHViMjk0IFx1ZDAwMFx1ZDJiOCBcdWQyYjhcdWI4MDhcdWM3NzRcdWI1MjkgXHVkNjhjXHVjMGFjXHVjNzc0XHViMmU0LiBIUlRcdWIyOTQgXHVjNWQ0XHVjOWMwXHViMmM4XHVjNWI0XHVjNjQwIFx1YzVmMFx1YWQ2Y1x1Yzc5MFx1YjRlNFx1Yzc3NCBcdWQ1NWMgXHVkMzAwXHVjNzQ0IFx1Yzc3NFx1YjkwNCBcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YmE3MCwgXHVhZTAwXHViODVjXHViYzhjIFx1YWUwOFx1YzczNSBcdWMyZGNcdWM3YTVcdWM1ZDBcdWMxMWMgXHViOWU0XHVjNzdjIFx1YzIxOFx1YmMzMVx1YjljYyBcdWM4ZmNcdWM3NTggXHVjOGZjXHVjMmRkXHVjNzQ0IFx1YWM3MFx1Yjc5OFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+SFJUXHVjNzU4IFx1YzJlMFx1Yzc4NSBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OTggXHVhYzFjXHViYzFjXHVjNzkwXHViMjk0IFx1YzBjOFx1Yjg1YyBcdWMxMjRcdWFjYzRcdWQ1NWMgXHVhYzcwXHViNzk4IFx1YzgwNFx1YjdiNVx1Yzc0NCBcdWI1MzBcdWI5NzRcdWIyOTQgXHVjMmRjXHVjN2E1XHVjODcwXHVjMTMxKG1hcmtldC1tYWtpbmcpIFx1YzVkNFx1YzljNFx1Yzc0NCBcdWFjMWNcdWJjMWNcdWQ1NWMgXHViNGE0LCBcdWFkZjggXHVjNWQ0XHVjOWM0XHVjNzU4IFx1YzU0OFx1YzgxNVx1YzEzMVx1Yzc0NCBcdWQzYzlcdWFjMDBcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWMyZGNcdWM3YTVcdWM4NzBcdWMxMzEgXHVjNWQ0XHVjOWM0XHVjNzQwIFx1YzhmY1x1YzJkZFx1Yzc0NCBcdWJjZjRcdWM3MjBcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWMwMFx1YzBjMVx1Yzc1OCBcdWFjYzRcdWM4OGNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YWM3MFx1Yjc5OFx1Yjk3YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzAsICROJFx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViOWU0XHViOWU0IFx1YzJkY1x1YzgxMChcdWQyZjEpXHVjNWQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjODA0XHViN2I1XHVjNzQ0IFx1YjUzMFx1Yjc3YyBcdWFjNzBcdWI3OThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JGkkXHViYzg4XHVjOWY4IFx1YjllNFx1YjllNCBcdWMyZGNcdWM4MTBcdWM1ZDAgXHVjNWQ0XHVjOWM0XHVjNzQwICRhX2kkIFx1Yzc3NFx1YzBjMSAkYl9pJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWM4MTVcdWMyMThcdWFjMDAgXHVjNTkxXHVjMjE4XHViNzdjXHViYTc0IFx1YWRmOFx1YjljY1x1ZDA3YyBcdWM4ZmNcdWMyZGRcdWM3NDQgXHViOWU0XHVjMjE4XHVkNTU4XHVhY2UwLCBcdWM3NGNcdWMyMThcdWI3N2NcdWJhNzQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWM4MDhcdWIzMTNcdWFjMTJcdWI5Y2NcdWQwN2MgXHVjOGZjXHVjMmRkXHVjNzQ0IFx1YjllNFx1YjNjNFx1ZDU1OFx1YWNlMCwgJDAkXHVjNzc0XHViNzdjXHViYTc0IFx1YzhmY1x1YzJkZFx1Yzc0NCBcdWI5ZTRcdWI5ZTRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3NzQgXHViNTRjIFx1YmNmNFx1YzcyMFx1ZDU1YyBcdWM4ZmNcdWMyZGRcdWM3NzQgXHViZDgwXHVjODcxXHVkNTc0XHViM2M0IFx1YjllNFx1YjNjNFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzAsIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHViY2Y0XHVjNzIwIFx1YzhmY1x1YzJkZFx1Yzc1OCBcdWMyMThcdWIyOTQgXHVjNzRjXHVjMjE4XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JGkkXHViYzg4XHVjOWY4IFx1YjllNFx1YjllNCBcdWM5YzFcdWQ2YzQgXHViY2Y0XHVjNzIwIFx1YzhmY1x1YzJkZFx1Yzc3NCAkMCRcdWM4ZmNcdWI3N2NcdWJhNzQsIFx1ZDU3NFx1YjJmOSBcdWM4MDRcdWI3YjVcdWM3NzQgXHVkM2VjXHVjOWMwXHVjMTU4IFx1YjE3OFx1Y2Q5Y1x1Yzc0NCBcdWNkNWNcdWMxOGNcdWQ2NTRcdWQ1NThcdWM1ZWMgXHVjNzA0XHVkNWQ4XHVjMTMxXHVjNzQ0IFx1YzY0NFx1ZDY1NFx1ZDU1OFx1YWNlMCBcdWMyZGNcdWM3YTUgXHVjNTQ4XHVjODE1XHVjMTMxXHVjNWQwIFx1YWUzMFx1YzVlY1x1ZDU4OFx1YjJlNFx1YWNlMCBcdWQzYzlcdWFjMDBcdWQ1NThcdWM1ZWMgXHVjMmRjXHVjN2E1XHVjODcwXHVjMTMxIFx1YzVkNFx1YzljNFx1Yzc1OCBcdWM1NDhcdWM4MTVcdWMxMzFcdWM3NzQgJHhfaSRcdWI5Y2NcdWQwN2MgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyMThcdWMyMThcdWI4Y2MgXHViNjEwXHViMjk0IFx1YzJhY1x1YjlhY1x1ZDUzY1x1YzljMCBcdWI0ZjEgXHViMmU0XHViOTc4IFx1YzY5NFx1YzE4Y1x1YjI5NCBcdWJhYThcdWI0NTAgXHViYjM0XHVjMmRjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Y2QxZCAkTiRcdWJjODhcdWM3NTggXHViOWU0XHViOWU0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWI5YzhcdWNjZTRcdWM3NDQgXHViNTRjLCBcdWMyZTBcdWFkZGMgXHVhYzFjXHViYzFjXHVkNTVjIFx1YzJkY1x1YzdhNVx1Yzg3MFx1YzEzMSBcdWM1ZDRcdWM5YzRcdWM3NzQgXHViMmVjXHVjMTMxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNTQ4XHVjODE1XHVjMTMxXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzhmY1x1YzJkZFx1Yzc0NCBcdWI5ZTRcdWI5ZTRcdWQ1NWMgXHVkNjlmXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgkMSBcXGxlcSBOIFxcbGVxIDFcXCwwMDBcXCwwMDAkKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJE4kXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAsIFx1YWRmOCBcdWM5MTEgJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkaSRcdWJjODhcdWM5ZjggXHViOWU0XHViOWU0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IFx1YzEzOCBcdWM4MTVcdWMyMTggJGFfaSwgYl9pLCB4X2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJC0xMF45IFxcbGVxIGFfaSBcXGxlcSBiX2kgXFxsZXEgMTBeOSQ7ICQxIFxcbGVxIHhfaSBcXGxlcSAxMF45JCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgJE4kXHViYzg4XHVjNzU4IFx1YjllNFx1YjllNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHViOWM4XHVjY2U0XHVjNzQ0IFx1YjU0YywgXHVjMmUwXHVhZGRjIFx1YWMxY1x1YmMxY1x1ZDU1YyBcdWMyZGNcdWM3YTVcdWM4NzBcdWMxMzEgXHVjNWQ0XHVjOWM0XHVjNzc0IFx1YjJlY1x1YzEzMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzU0OFx1YzgxNVx1YzEzMVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM0MDU3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFya2V0LU1ha2luZyIsImRlc2NyaXB0aW9uIjoiPHA+SFJUIGlzIGZpcnN0IGFuZCBmb3JlbW9zdCBhIG1hdGggYW5kIHRlY2hub2xvZ3kgY29tcGFueS4gV2UgYXJlIGVuZ2luZWVycyBhbmQgcmVzZWFyY2hlcnMgd29ya2luZyBhcyBvbmUgdGVhbSB0byBzb2x2ZSBkaWZmaWN1bHQgcHJvYmxlbXMsIGFuZCB0cmFkaW5nIG1pbGxpb25zIG9mIHNoYXJlcyBhIGRheSBvbiB0aGUgd29ybGQmcnNxdW87cyBmaW5hbmNpYWwgbWFya2V0cy48XC9wPlxyXG5cclxuPHA+QSBuZXcgZW1wbG95ZWUgYXQgSFJUIGhhcyBkZXZlbG9wZWQgYSBtYXJrZXQtbWFraW5nIGVuZ2luZSBiYXNlZCBvbiB0aGUgbmV3bHkgZGVzaWduZWQgdHJhZGluZyBzY2hlbWUuIFRoZSBkZXZlbG9wZXIgd2lzaGVzIHRvIGFuYWx5emUgdGhlIHN0YWJpbGl0eSBvZiB0aGUgbmV3IGVuZ2luZS4gVGhlIGVuZ2luZSB1c2VzIGEgdmlydHVhbCBhY2NvdW50IChpbml0aWFsbHkgaG9sZGluZyBubyBzaGFyZXMpIGZvciB0cmFkaW5nIGFuZCB3aWxsIGZvbGxvdyB0aGUgc3RyYXRlZ3kgYmVsb3cgZm9yICROJCBjb250aWd1b3VzIHRyYW5zYWN0aW9uIHBlcmlvZHMgKHRpY2tzKS48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BdCB0aGUgJGkkLXRoIHRyYW5zYWN0aW9uIHRpY2ssIHRoZSBlbmdpbmUgc2VsZWN0cyBhbiBpbnRlZ2VyIGJldHdlZW4gJGFfaSQgYW5kICRiX2kkLCBpbmNsdXNpdmUuIElmIHRoZSBzZWxlY3RlZCBpbnRlZ2VyIGlzIHBvc2l0aXZlLCBpdCBidXlzIGFuIGVxdWFsIG51bWJlciBvZiBzaGFyZXMgYXMgdGhlIGludGVnZXIuIElmIGl0IGlzIG5lZ2F0aXZlLCB0aGUgZW5naW5lIHNlbGxzIGFuIGVxdWFsIG51bWJlciBvZiBzaGFyZXMgYXMgdGhlIGFic29sdXRlIHZhbHVlIG9mIHRoZSBpbnRlZ2VyLiBJZiBpdCBpcyAkMCQsIHRoZSBlbmdpbmUgZG9lcyBub3QgbWFrZSBhIHRyYW5zYWN0aW9uLiBTaGFyZXMgY2FuIGJlIHNvbGQgZXZlbiBpZiB0aGUgZW5naW5lIGRvZXMgbm90IGhvbGQgYSBzdWZmaWNpZW50IGFtb3VudCwgYW5kIGluIHRoaXMgc2NlbmFyaW8sIHRoZSBudW1iZXIgb2Ygc2hhcmVzIGhlbGQgYmVjb21lcyBuZWdhdGl2ZS48XC9saT5cclxuXHQ8bGk+SWYgdGhlIG51bWJlciBvZiBzaGFyZXMgaGVsZCByaWdodCBhZnRlciB0aGUgJGkkLXRoIHRyYW5zYWN0aW9uIGlzICQwJCwgdGhlIHRyYWRpbmcgc2NoZW1lIGlzIGNvbnNpZGVyZWQgdG8gaGF2ZSBtaW5pbWl6ZWQgcG9zaXRpb24gZXhwb3N1cmUgYW5kIHRodXMgY29udHJpYnV0ZWQgdG8gbWFya2V0IHN0YWJpbGl0eS4gSW4gdGhpcyBjYXNlLCB0aGUgc3RhYmlsaXR5IG9mIHRoZSBlbmdpbmUgaW5jcmVhc2VzIGJ5ICR4X2kkLjxcL2xpPlxyXG5cdDxsaT5BbGwgb3RoZXIgZmFjdG9ycywgc3VjaCBhcyBmZWVzIG9yIHNsaXBwYWdlLCBhcmUgaWdub3JlZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5GaW5kIHRoZSBtYXhpbXVtIHN0YWJpbGl0eSB0aGUgbmV3IG1hcmtldC1tYWtpbmcgZW5naW5lIGNhbiBhY2hpZXZlIGFmdGVyIGFsbCAkTiQgdHJhbnNhY3Rpb25zIGhhdmUgYmVlbiBjb21wbGV0ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRyYW5zYWN0aW9ucyAkTiQuICgkMSBcXGxlcSBOIFxcbGVxIDFcXCwwMDBcXCwwMDAkKTxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBmb2xsb3dpbmcgJE4kIGxpbmVzIGNvbnRhaW5zIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyAkYV9pLCBiX2ksIHhfaSQsIGRlbm90aW5nIHRoZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgJGkkLXRoIHRyYW5zYWN0aW9uLiAoJC0xMF45IFxcbGVxIGFfaSBcXGxlcSBiX2kgXFxsZXEgMTBeOSQ7ICQxIFxcbGVxIHhfaSBcXGxlcSAxMF45JCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWF4aW11bSBzdGFiaWxpdHkgdGhlIG5ldyBtYXJrZXQtbWFraW5nIGVuZ2luZSBjYW4gYWNoaWV2ZSBhZnRlciBhbGwgJE4kIHRyYW5zYWN0aW9ucyBoYXZlIGJlZW4gY29tcGxldGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=